Problem Statement
Let $G_n$ be the unit distance graph in $\mathbb{R}^n$, with two vertices joined by an edge if and only if the distance between them is $1$.
Estimate the chromatic number $\chi(G_n)$. Does it grow exponentially in $n$? Does\[\lim_{n\to \infty}\chi(G_n)^{1/n}\]exist?
Estimate the chromatic number $\chi(G_n)$. Does it grow exponentially in $n$? Does\[\lim_{n\to \infty}\chi(G_n)^{1/n}\]exist?
Categories:
Graph Theory Geometry Chromatic Number
Progress
A generalisation of the Hadwiger-Nelson problem (which addresses $n=2$). Frankl and Wilson [FrWi81] proved exponential growth:\[\chi(G_n) \geq (1+o(1))1.2^n.\]The trivial colouring (by tiling with cubes) gives\[\chi(G_n) \leq (2+\sqrt{n})^n.\]Larman and Rogers [LaRo72] improved this to\[\chi(G_n) \leq (3+o(1))^n,\]and conjecture the truth may be $(2^{3/2}+o(1))^n$. Prosanov [Pr20] has given an alternative proof of this upper bound.See also [508], [705], and [706].
Source: erdosproblems.com/704 | Last verified: January 16, 2026