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 $\chi$($\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$\le$$\chi$($\mathbb {E}$²)$\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}$³)$\le$15. See [Gra04a,Gra04b] for further results and references.

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.

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.