Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 .

share|improve this question

4 Answers 4

up vote 8 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.