Statement:

How many colors are needed to paint the plane so that no two points a unit distance apart are painted the same color?

-Equivalently-

What is the chromatic number \(\chi \left(\mathbb{E}^2 \right) \) 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.

Author	Date Published	Prize	Paid By
Hadwider and Edward Nelson	1944	$1,000	Ron Graham [1] [2]

Partial Results:

Erdős and de Bruijn showed [3] that the chromatic number of the plane is attained for some finite subgraph of G. This led to narrowing the answer to \(4\leq \chi \left(\mathbb{E}^2 \right)\leq7 \)
The lower bound was further refined by Aubrey D. N. J. de Grey in 2018 [7] to be at least 5.

Left: The 1581-vertex, non-4-colourable unit-distance graph G. Aubrey de Grey [7]
Right:The Moser spindle embedded as a unit distance graph in the plane, together with a seven-coloring of the plane. Image Credit: David Eppstein

Related Problems:

Q908004 Chromatic Number of \(\mathbb{R}^3 \)
Q908005 Chromatic Number of \(\mathbb{R}^n \)
Monochromatic Triangles

References:

[1] 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.

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

[3] 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.

[4] 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.

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

[6] The Open Problems Project, Erik D. Demaine, Joseph S. B. Mitchell, Joseph O’Rourke https://topp.openproblem.net/

[7] Aubrey D. N. J. de Grey The chromatic number of the plane is at least 5. arXiv:1804.02385 [math.CO], 2018.

Keywords:

Combinatorial Geometry; chromatic number; unit-distance graph