Chromatic number of the plane
Description of constant
$C_{27}$ is the chromatic number of the plane, usually denoted $\chi(\mathbb R^{2})$ (the Hadwiger–Nelson problem).
Equivalently, let $U_{2}$ be the unit-distance graph on $\mathbb R^{2}$: its vertex set is $\mathbb R^{2}$, with an edge between distinct points $x,y\in\mathbb R^{2}$ iff $|x-y|_{2}=1$. Then
\[C_{27} \ :=\ \chi(\mathbb R^{2}) \ :=\ \chi(U_{2}),\]i.e. $C_{27}$ is the smallest integer $k$ such that there exists a map $c:\mathbb R^{2}\to{1,\dots,k}$ satisfying $c(x)\neq c(y)$ whenever $|x-y|_{2}=1$.
It is known that
\[5\ \le\ C_{27}\ \le\ 7.\]Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $7$ | [Had1945], [CR2017] | A periodic $7$-coloring obtained from a tiling of the plane by small regular hexagons (historically attributed to Isbell, 1950). |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $3$ | Trivial | An equilateral triangle of side length $1$ forces three colors. |
| $4$ | [MM1961] | Moser spindle: a $7$-vertex unit-distance graph with chromatic number $4$. |
| $5$ | [deG2018] | First proof that $\chi(\mathbb R^{2})\ge 5$, via an explicit finite unit-distance graph. |
Additional comments and links
-
The main open question is whether $C_{27}\in{5,6,7}$.
-
Finite reduction (with choice). Since $C_{27}\le 7$, the de Bruijn–Erdős theorem [dBE1951] implies (assuming the axiom of choice) that $C_{27}$ is attained by some finite unit-distance graph in the plane. In particular, under choice, $C_{27}$ equals the maximum chromatic number among finite unit-distance graphs in $\mathbb R^{2}$.
-
Known $5$-chromatic unit-distance graphs. de Grey’s original construction had $1581$ vertices [deG2018]. Subsequent computer-aided work produced substantially smaller $5$-chromatic examples; see e.g. [Heu2018] and the Polymath16 project page.
-
Witness sizes for $7$ colors. If $C_{27}=7$, then there must exist a finite $7$-chromatic unit-distance graph. Quantitative lower bounds on the minimum number of vertices needed for such a graph are known; see [Pri1998].
-
Set-theoretic issues. The de Bruijn–Erdős reduction uses choice, and without it chromatic phenomena for related distance graphs can depend on the axioms of set theory; see [SS2003], [SS2004].
- Wikipedia page on the Hadwiger–Nelson problem
- Polymath16 page
References
-
[CR2017] Cranston, Daniel W.; Rabern, Landon. The fractional chromatic number of the plane. Combinatorica 37 (2017), no. 5, 837–861. arXiv:1501.01647
-
[dBE1951] de Bruijn, N. G.; Erdős, P. A colour problem for infinite graphs and a problem in the theory of relations. Indag. Math. 13 (1951), 371–373.
-
[deG2018] de Grey, Aubrey. The chromatic number of the plane is at least 5. Geombinatorics 28 (2018), no. 1, 18–31. arXiv:1804.02385
-
[EI2020] Exoo, Geoffrey; Ismailescu, Dan P. The chromatic number of the plane is at least 5: A new proof. Discrete & Computational Geometry 64 (2020), 216–226. arXiv:1805.00157
-
[Had1945] Hadwiger, Hugo. Überdeckung des Euklidischen Raumes durch kongruente Mengen. Portugaliae Math. 4 (1945), 238–242.
-
[Heu2018] Heule, Marijn J. H. Computing small unit-distance graphs with chromatic number 5. arXiv:1805.12181 (2018).
-
[MM1961] Moser, L.; Moser, W. Solution to Problem 10. Canadian Mathematical Bulletin 4 (1961), 187–189.
-
[Pri1998] Pritikin, David. All unit-distance graphs of order 6197 are 6-colorable. J. Combin. Theory Ser. B 73 (1998), no. 2, 159–163.
-
[SS2003] Shelah, Saharon; Soifer, Alexander. Axiom of choice and chromatic number of the plane. J. Combin. Theory Ser. A 103 (2003), no. 2, 391–397.
-
[SS2004] Soifer, Alexander; Shelah, Saharon. Axiom of choice and chromatic number: examples on the plane. J. Combin. Theory Ser. A 105 (2004), 359–364. DOI: 10.1016/j.jcta.2004.01.001.
Contribution notes
Prepared with assistance from ChatGPT 5.2 Pro.