Next: Problem 58: Monochromatic Triangles
Previous: Problem 56: Packing Unit Squares in a Simple Polygon
How many colors are needed to paint the plane so that no two points a unit distance apart are painted the same color? If the same question is asked of the line, the answer is 2: Coloring [0,1) red, [1,2) blue, etc., ensures that no two unit-separated points have the same color. One can view the question as asking for the chromatic number \chi(\mathbb{E}^2) of the infinite unit-distance graph G, with every point in the plane a vertex, and an edge between two vertices if they are separated by a unit distance.
Hadwider and Edward Nelson, 1944.
Open. Erdős and de Bruijn showed [EdB51] that the chromatic number of the plane is attained for some finite subgraph of G. This result led to narrowing the answer to 4 \le \chi(\mathbb{E}^2) \le 7. For example, the lower bound of 4 is established by the “Moser graph.”
The knowledge gap for the chromatic number of (3D) space is even wider than for the plane: it is only known to satisfy 6 \le \chi(\mathbb{E}^3) \le 15. See [Gra04a], [Gra04b] for further results and references.
There is now some evidence that the chromatic number of the plane may depend on the axioms of set theory. This was first seen possible in examples constructed by Saharon Shelah and Alexander Soifer. Now Payne [Pay09] has constructed unit-distance graphs with the same property.
Ron Graham offers $1000 for a solution.
combinatorial geometry
J. O’Rourke, 15 Aug. 2004; 6 July 2009.
P. Erdős and N. G. de Bruijn. A colour problem for infinite graphs and a problem in the theory of relations. Indag. Math., 13:371–373, 1951.
R. L. Graham. Open problems in Euclidean Ramsey theory. Geocombinatorics, XIII(4):165–177, April 2004.
R. L. Graham. Euclidean Ramsey theory. In Jacob E. Goodman and Joseph O’Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 11, pages 239–254. CRC Press LLC, Boca Raton, FL, 2nd edition, 2004.
Joseph O’Rourke. Computational geometry column 46. Internat. J. Comput. Geom. Appl., 14(6):475–478, 2004. Also in SIGACT News, 35(3):42–45 (2004), Issue 132.
M. S. Payne. Unit distance graphs with ambiguous chromatic number. arXiv:0707.1177v2 [math.CO], 2009.