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.
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. A54,
371-373, 1951.de Grey, A. D. N. J. "The Chromatic
Number of the Plane Is at Least 5." Geombinatorics28, No. 1,
18-31, 2018.Erdős, P.; Harary, F.; and Tutte, W. T. "On
the Dimension of a Graph." Mathematika12, 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." Geombinatorics28, 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." Geombinatorics29, 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. A103, 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.