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