Chromatic number of the plane
The unit-distance graph of the plane has every point of $\mathbb{R}^2$ as a vertex, two points being adjacent when their distance is $1$; its chromatic number is denoted $\chi(\mathbb{E}^2)$. On the line two colors suffice: color the intervals $[k, k+1)$, $k \in \mathbb{Z}$, alternately.
Erdős and de Bruijn proved that some finite unit-distance graph in the plane already needs $\chi(\mathbb{E}^2)$ colors, and the bounds $4 \le \chi(\mathbb{E}^2) \le 7$ followed, the lower one from the Moser graph; de Grey has since raised the lower bound to $5$. For three-dimensional space only $6 \le \chi(\mathbb{E}^3) \le 15$ is known. Examples of Shelah and Soifer, and unit-distance graphs constructed by Payne, suggest that the answer may depend on the axioms of set theory.
Problem. What is the least number of colors with which the plane can be colored so that no two points at distance $1$ receive the same color, that is, what is $\chi(\mathbb{E}^2)$?
Source: Hadwiger and Nelson (1944); Problem 57 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- chromatic number of the plane, Hadwiger–Nelson problem, The Open Problems Project, unit-distance graph
References
@misc{degrey2018,
author = {de Grey, Aubrey D. N. J.},
title = {The chromatic number of the plane is at least 5},
year = {2018},
eprint = {1804.02385},
archivePrefix = {arXiv},
}
@article{erdos1951,
author = {Erd{\H{o}}s, P. and de Bruijn, N. G.},
title = {A colour problem for infinite graphs and a problem in the theory of relations},
journal = {Indag. Math.},
volume = {13},
year = {1951},
pages = {371--373},
}
@incollection{graham2004handbook,
author = {Graham, R. L.},
title = {Euclidean {R}amsey theory},
booktitle = {Handbook of Discrete and Computational Geometry},
edition = {2nd},
editor = {Goodman, Jacob E. and O'Rourke, Joseph},
publisher = {CRC Press LLC},
address = {Boca Raton, FL},
year = {2004},
pages = {239--254},
}
@article{graham2004geocombinatorics,
author = {Graham, R. L.},
title = {Open problems in {E}uclidean {R}amsey theory},
journal = {Geocombinatorics},
volume = {13},
number = {4},
year = {2004},
pages = {165--177},
}
@misc{payne2009,
author = {Payne, M. S.},
title = {Unit distance graphs with ambiguous chromatic number},
year = {2009},
eprint = {0707.1177},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/0707.1177v2},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01096, "Chromatic number of the plane", clopen.solutions.