From: cet1@cus.cam.ac.uk (Chris Thompson)
Newsgroups: sci.math
Subject: Re: On coloring the real plane.
Date: 27 Aug 1995 00:30:16 GMT

In article <1995Aug26.144241.13777@jarvis.cs.toronto.edu>, fpitt@cs.toronto.edu 
(Francois Pitt) writes:
|>   This is something that I posted to `rec.puzzles'.  Someone there
|> (sorry, I can't remember who) told me it was an unsolved problem, and
|> someone else suggested that I post it here.  I already checked in the
|> FAQ and I didn't see this, so here goes!
|> 
|>   Say you want to assign a color to every point in the real plane (i.e.,
|> every pair (x,y) where x and y are real numbers), in such a way that the
|> following property holds:
|> 
|>     For every two points a and b, if the distance between a and b
|>     is equal to 1, then a and b are _not_ the same color.
|> 
|>   There is an elegant proof that this cannot be done with 3 colors or
|> less, and I have found a simple coloring using 7 colors.  The question
|> now is: what is the mininum number of colors required?  (In other words,
|> can this be done with 4, 5, 6 colors or not?)

For a review of the status (as of 1990) of this and several related problems,
check section G10 in [1]. Specifically

  Nothing better than 4 <= #colours <= 7 is known unless some 
    restrictions are placed on the sets of points with a fixed colour.

  If these sets are required to be Lesbesgue measurable, then 
    Falconer has proved #colours >= 5

  If the sets are unions of regions bounded by rectifiable Jordan curves    
    (with the points on the boundaries assigned to some neighbouring
    region) then Woodall has proved #colours >= 6

[1] Hallard T. Croft, Kenneth J. Falconer, Richard K. Guy
    Unsolved Problem In Geometry
    Springer-Verlag (1991)
    ISBN 0-387-97506-3

Chris Thompson
Email: cet1@cus.cam.ac.uk