Hadwiger-Nelson Problem

The Hadwiger-Nelson problem asks for the chromatic number of the plane, i.e., the minimum number of colors needed to color the plane if no two points at unit distance one from one another are given the same color. The problem was first discussed (though not published) by Nelson in 1950 (Soifer 2008, de Grey 2018). Since that time, the exact answer was known to be 4, 5, 6, or 7, with the lower bound provided by unit-distance graphs such as the Moser spindle and Golomb graph (both of which have chromatic number 4), and the upper bound by the tiling of the plane by congruent regular hexagons tiling the plane (which can be assigned seven colors in a pattern that separates all same-colored pairs of tiles by more than their diameter), as first observed by Isbell in 1950 and discussed in different context by Hadwiger (1945; Soifer 2008, de Grey 2018).

The first unit-distance graphs with chromatic number of five or larger was constructed by de Grey (2018). The smallest of these was reduced from a larger example to a graph on 1581 vertices, here called the de Grey graph. The existence of this graph established that the chromatic number of the plane is 5, 6, or 7. Following the publication of de Grey's graph, smaller non-4-colorable unit-distance graphs derived from it were discovered by Dustin Mixon, Marijn Heule, and Jaan Parts in the ensuing days, weeks, months, and years.

REFERENCES

Chilakamarri, K. B. "The Unit-Distance Graph Problem: A Brief Survey and Some New Results." Bull Inst. Combin. Appl. 8, 39-60, 1993.

Coulson, D. "On the Chromatic Number of Plane Tilings." J. Austral. Math. Soc. 77, 191-196, 2004.

Coulson, D. (2002), "A 15-colouring of 3-space omitting distance one", Discrete Math. 256: 83-90, 2002.

Croft, H. T.; Falconer, K. J.; and Guy, R. K. Problem G10 in Unsolved Problems in Geometry. New York: Springer-Verlag, 1991.

de Bruijn, N. G. and Erdős, P. "A Colour Problem for Infinite Graphs and a Problem in the Theory of Relations." Nederl. Akad. Wetensch. Proc. Ser. A 54, 371-373, 1951.

de Grey, A. D. N. J. "The Chromatic Number of the Plane Is at Least 5." Geombinatorics 28, No. 1, 18-31, 2018.

Erdős, P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.

Exoo, G. and Ismailescu, D. "The Chromatic Number of the Plane Is at Least 5: A New Proof." Disc. Comput. Geom. 64, 216-226, 2020.

Gardner, M. "Mathematical Games." Sci. Amer. 203, 180, 1960.

Hadwiger, H. "Überdeckung des euklidischen Raumes durch kongruente Mengen." Portugal. Math. 4, 238-242, 1945.

Hadwiger, H. "Ungelöste Probleme No. 40." Elem. Math. 16, 103-104, 1961.

Heule, M. J. H. "Computing Small Unit-Distance Graphs with Chromatic Number 5." Geombinatorics 28, 32-50, 2018.

Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, pp. 150-152, 1995.

Lamb, E. "Decades-Old Graph Problem Yields to Amateur Mathematician." Quanta Mag. Apr. 17, 2018.

 https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/.Mixon, D. G. "Polymath16, First Thread: Simplifying De Grey's Graph." 14 Apr 2018.

 https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread-simplifying-de-greys-graph/.Parts, J. "Graph Minimization, Focusing on the Example of 5-Chromatic Unit-Distance Graphs in the Plane." Geombinatorics 29, No. 4, 137-166, 2020.

PolyMath. "Hadwiger-Nelson Problem." http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem.Shelah, S. and Soifer, A. "Axiom of Choice and Chromatic Number of the Plane." J. Combin. Th., Ser. A 103, 387-391, 2003.

Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2008.Soifer, A. "Breakthrough in My Favorite Open Problem of Mathematics: Chromatic Number of the Plane." https://www.cs.umd.edu/~gasarch/BLOGPAPERS/soifer.pdf.