# A variant to the Hadwiger-Nelson problem

Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$.

What is $\chi(G)$?

(This is a variant of the Hadwiger-Nelson problem.)

• Wow, it is a coloring problem in an infinite graph! The key point is the distribution relationship between R and Q. Interesting! – Rupei Xu Feb 23 '15 at 8:38

By considering all the rational numbers on the $x$-axis we can see that we need at least countably many colors. This is also sufficient, that is the chromatic number of the rational-distances graph is countable. This is due to Erdos and Hajnal in the case of $\mathbb R^2$. They show that the rational-distances graph in the plane does not contain a copy of the complete bipartite graph $K(2,\omega_1)$, and that any such graph must have countable chromatic number.
The result was generalized to rational distances graphs in $\mathbb R^n$ by Peter Komjath. However, the previous method doesn't generalize since now the graph contains even a copy of $K(\omega, 2^\omega)$. Instead, Komjath uses a clever transfinite induction argument.
P. Komjath, "A decomposition theorem for $\mathbb R^n$" Proc. Amer. Math. Society (1994): 921-927.