Serious applications of Colouring proofs

Question

Are there any research-level applications of proofs by colouring?

This is the kind of proof you use to show that you can't cover a mutilated chessboard with 31 dominoes. Afaik, this technique chiefly finds a market in IMO preparation classes; see Arthur Engel's book or this handout .

score 10 · Accepted Answer · answered Apr 14 '11 at 06:40

I don't think you can formally distinguish "proofs by coloring" from "parity arguments" or more generally arguments that use some mapping into a finite domain, say be reducing mod m. Coloring is just a visually appealing way of looking at such an argument. Needless to say, proofs by parity arguments or other mappings into a finite set are very common; this is a fundamental tool in combinatorics and number theory.

lhf · Answer 2 · 2011-05-17T01:51:41.847

4

Sperner's lemma has several applications, including the effective computation of fixed points and a constructive proof of the Brouwer fixed point theorem.

edited May 17 '11 at 01:51

answered Apr 14 '11 at 10:18

lhf

216,483

score 2 · Answer 3 · edited May 17 '11 at 13:57

2

Conway's Soldiers is a proof-by-coloring with an infinity of colors.

edited May 17 '11 at 13:57

J. M. ain't a mathematician

75,051

answered May 17 '11 at 06:11

Gerry Myerson

179,216

This is nice. I think the link might not be exactly what you meant it to be, though? – Aaron Mazel-Gee May 17 '11 at 06:53
I cut'n'pasted but the last part of the URL didn't become part of the link. I'm hoping someone who knows more about these things than I do (and that's setting the bar pretty low) will come along and fix the link. – Gerry Myerson May 17 '11 at 06:57
http://en.wikipedia.org/wiki/Conway%27s_Soldiers – Dan Brumleve May 17 '11 at 07:09
you can use this syntax for links: [link](url), as in Conway's Soldiers. – lhf May 17 '11 at 10:47

score 1 · Answer 4 · answered May 17 '11 at 14:07

There is a vertex coloring argument that is used in Steve Fisk's elegant proof of the Chvatal-Klee-Art Gallery Theorem: http://en.wikipedia.org/wiki/Art_gallery_problem The coloring argument can be extended to handle the case where the art gallery is a rectilinear (orthogonal) polygon.

Serious applications of Colouring proofs

4 Answers4