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.