The odd-distance plane graph

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