# Serious applications of Colouring proofs

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 .

-

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.

-

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

-

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

-
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 6: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 6:57
you can use this syntax for links: [link](url), as in Conway's Soldiers. – lhf May 17 '11 at 10:47

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.

-