Chromatic number of the plane (Hadwiger–Nelson problem)

Bondy–Murty, Graph Theory, Appendix A, item 54 · Colouring graphs embedded in surfaces

Bondy–Murty Problem — first stated 1950

Attributed to: E. Nelson

Status partial high confidence

The exact chromatic number of the plane remains unknown. De Grey (2018) improved the lower bound from 4 to 5 by constructing a 1581-vertex unit-distance graph that is not 4-colourable, so the current range is 5 ≤ χ(ℝ²) ≤ 7. Subsequent work (Heule 2018, Polymath16 2021) reduced the smallest known witness to 509 vertices, but no progress on the upper bound has been made. For the map-type colouring variant (regions bounded by non-unit-circle arcs with trivalent vertices), Sokolov–Voronov (2025) proved a lower bound of 7, but this does not settle the point-colouring formulation.

Cited literature (3)

partial The chromatic number of the plane is at least 5 (2018)

Aubrey D.N.J. de Grey · Geombinatorics, vol. 28, pp. 5–18 · arXiv:1804.02385

Constructs a finite unit-distance graph in the plane with chromatic number 5, proving χ(ℝ²) ≥ 5 and raising the lower bound from 4 to 5.
partial Computing Small Unit-Distance Graphs with Chromatic Number 5 (2018)

Marijn J.H. Heule · arXiv preprint · arXiv:1805.12181

Uses SAT-solver methods to find 553-vertex unit-distance graphs with chromatic number 5, significantly reducing de Grey's original 1581-vertex construction.
partial On the chromatic number of the plane for map-type colorings (2025)

Georgy Sokolov, Vsevolod Voronov · arXiv preprint · arXiv:2502.01958

Proves that at least 7 colours are required for map-type colorings of the plane (regions bounded by non-unit-circle arcs, trivalent vertices), a variant stronger than the standard point-colouring formulation.

Reviewer notes. The book states 4 ≤ χ(ℝ²) ≤ 7; de Grey's 2018 result tightens this to 5 ≤ χ(ℝ²) ≤ 7. The Polymath16 collaborative project (2019–2021) reduced the smallest known 5-chromatic unit-distance graph to 509 vertices (as of 2021). The related OPG record 'coloring_the_odd_distance_graph' concerns the analogous problem for odd distances and is a distinct (open) problem. The map-type colouring result of Sokolov–Voronov (2025) applies to a stronger geometric variant and does not settle the standard point-colouring version. Web search was unavailable; WebFetch calls were used directly on arXiv and Wikipedia.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).

Problem. Determine the chromatic number of the unit-distance graph of the plane, i.e. the least number of colours needed to colour the points of $\mathbb{R}^2$ so that no two points at distance $1$ receive the same colour.

Context

At the time of the book, $4 \le \chi(\mathbb{R}^2) \le 7$.

In the book: Exercise 15.1.20.

Related records in this index

This conjecture was absent from the Open Problem Garden and arXiv corpora; the records below are the nearest ones.

Coloring the Odd Distance Graph — odd-distance analogue

Editorial notes. Editorial lead, to be confirmed by the status review: de Grey (2018) showed the chromatic number is at least 5.

Source

Théorie des graphes (J.A. Bondy, U.S.R. Murty; French edition by Frédéric Havet, 2025), Appendix A « Problèmes ouverts »
Item 54, book p. 631 (PDF p. 647) · https://inria.hal.science/hal-05211979v1 · PDF
English edition: J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer 2008, Appendix A.