Problem 57: Chromatic Number of the Plane

Statement

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 χ($\mathbb {E}$²) 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.

Origin

Hadwider and Edward Nelson, 1944.

Status/Conjectures

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≤χ($\mathbb {E}$²)≤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≤χ($\mathbb {E}$³)≤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.

Related Open Problems

Problem 58.

Reward

Ron Graham offers $1000 for a solution.

Appearances

[O'R04]

Categories

combinatorial geometry

Entry Revision History

J. O'Rourke, 15 Aug. 2004; 6 July 2009.

Bibliography

EdB51

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.

Gra04b

R. L. Graham.
Open problems in Euclidean Ramsey theory.
Geocombinatorics, XIII(4):165-177, April 2004.

Gra04a

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.

O'R04

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.

Pay09

M. S. Payne.
Unit distance graphs with ambiguous chromatic number.
arXiv:0707.1177v2 [math.CO], 2009.