Erdős Problem #706

declared status 'open'. Formalized: no. 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)}$? Current best: The case $r=1$ is the Hadwiger-Nelson problem, for which it is known that $5\leq L(1)\leq 7$. Prize: no. Tags: chromatic number, graph theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.