4
$\begingroup$

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 .

4 Answers 4

9

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.

4

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

2

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

  • 0
    you can use this syntax for links: `[link](url)`, as in [Conway's Soldiers](http://en.wikipedia.org/wiki/Conway's_Soldiers).2011-05-17
1

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.