Skip to main content
1 of 2
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

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$:

P. Erdos and A. Hajnal, "On chromatic number of graphs and set systems", Acta Math. Hungar. 17(1966), 61-99.

This was generalized to $\mathbb R^n$ by Peter Komjath in

P. Komjath, "A decomposition theorem for $\mathbb R^n$" Proc. Amer. Math. Society (1994): 921-927.

Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402