Skip to main content
added 494 characters in body
Source Link
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$:. 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.

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

ThisThe result was generalized to rational distances graphs in $\mathbb R^n$ by Peter Komjath in. 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$""A decomposition theorem for $\mathbb R^n$" Proc. Amer. Math. Society (1994): 921-927.

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.

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.

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

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.

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