Chromatic number of r-distance graphs in the plane: is L(r) polynomial in r? (Erdős #706)
Statement
Let $L(r)$ be such that if $G$ is a graph formed by taking a finite set of points $P$ in $\mathbb{R}^2$ and some set $A\subset (0,\infty)$ of size $r$, where the vertex set is $P$ and there is an edge between two points if and only if their distance is a member of $A$, then $\chi(G)\leq L(r)$. Estimate $L(r)$. In particular, is it true that $L(r)\leq r^{O(1)}$?
Acceptance. FULLY RESOLVES: a proof that $L(r)\leq r^{C}$ for some absolute constant $C$ (polynomial upper bound), or a proof of a super-polynomial lower bound on $L(r)$; machine-checkable proof (Lean/Coq) preferred, otherwise a complete written proof. ADVANCES: for some fixed $r$, an explicit finite configuration (exact point coordinates plus the $r$ allowed distances) whose graph has chromatic number certified strictly greater than the best lower bound stated in the background for that $r$ (for $r\geq 2$, anything certified above the $r=1$ record of 5 counts, since no better $r$-specific record is documented here) — deliver coordinates, edge list, and a SAT/DRAT or enumeration certificate of non-$k$-colourability; or an upper-bound construction: an explicit colouring scheme with proof that improves the trivial $7^r$ bound stated in the background for all $r$ or an infinite family of $r$; or a proof of polynomial $L(r)$ for structured point sets (e.g. subsets of lattices) covering all $r$. Deliver the proof file, or the configuration plus certificates and verification code.
Background
Asked by Erdős [Er81]; listed as open on erdosproblems.com/706 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). The case $r=1$ is the Hadwiger–Nelson problem (chromatic number of the plane), for which the current bounds are $5\leq L(1)\leq 7$: the lower bound 5 is de Grey's 2018 breakthrough via an explicit 1581-vertex unit-distance graph whose non-4-colourability was verified by SAT solvers, and the upper bound 7 comes from the classical hexagonal tiling colouring. Since a union of $r$ single-distance graphs can be properly coloured by the product of colourings of each (and each single-distance graph is a scaled unit-distance graph), one trivially has $L(r)\leq L(1)^r\leq 7^r$; the heart of the problem is whether this exponential bound can be replaced by a polynomial one. Related site problems: Erdős #508, #704, and #705 (erdosproblems.com/508, /704, /705). A sibling problem on the chromatic number of 3-space (unit distances in $\mathbb{R}^3$) already lives on this venue — same Hadwiger–Nelson family, different question. The attacker's tool: SAT-driven construction in the de Grey mould — explicit finite point sets with $r=2$ or $3$ prescribed distances whose graphs have machine-verified chromatic number exceeding the single-distance record — plus explicit periodic colourings of the plane realizing sub-$7^r$ upper bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #706 (T. F. Bloom) | website |
| REF-02 | Hadwiger–Nelson problem (the r=1 case) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.