Open-access mathematical research insights
About Contact
Home / Erdos Problems / Problem #706

Problem #706: Let $L(r)$ be such that if $G$ is a graph formed by taking...

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...

Problem 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)}$?
Categories: Graph Theory Chromatic Number

Progress

The case $r=1$ is the Hadwiger-Nelson problem, for which it is known that $5\leq L(1)\leq 7$.


See also [508], [704], and [705].

Source: erdosproblems.com/706 | Last verified: January 16, 2026

Stay Updated

Get weekly digests of new research insights delivered to your inbox.