Hadwiger-Nelson Problem

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

The first known unit-distance graph with chromatic number 5 was constructed by de Grey (2018). After a correction, the smallest graph in his construction had 1581 vertices and is called the de Grey graph in this work. The existence of this graph established that the chromatic number of the Euclidean plane is 5, 6, or 7. Following its publication, the record was progressively improved by the Mixon graphs, Heule graphs, and Parts graphs. As of August 2026, the smallest known unit-distance graph with chromatic number 5 realized in the Euclidean plane remains the 509-vertex Parts graph (Parts 2020, Haugland 2026). No unit-distance graph realized in the Euclidean plane with chromatic number greater than 5 is currently known.

Voronov et al. (2022) constructed -vertex examples containing no Moser spindle. Haugland (2026) reduced the vertex count under this additional restriction to 2131; this does not improve the unrestricted record.

The following table gives each successive strict improvement in the smallest known vertex count among unit-distance graphs with chromatic number 5, beginning with the corrected de Grey graph. Graphs that improved only the edge count at an already attained vertex count are not included.