The odd-distance plane graph

by Ardal and Manuch and Rosenfeld and Shelah and Stacho. [AMRShS:923]
Discrete and Computational Geometry, 2009
The vertices of the odd-distance graph are the points of the plane {R}^2 . Two points are connected by an edge if their Euclidean distance is an odd integer. We prove that the chormatic number of this graph is at least five. We also prove that the odd-distance graph in {R}^2 is countably choosable, which such a graph in {R}^3 is not.

Back to the list of publications