Damásdi Gábor: Odd wheels are not odd-distance graphs

    
Abstract: Analogously to unit-distance graphs we define odd-distance graphs to be graphs that can be drawn in the plane with (possibly intersecting) straight line segments such that the length of each edge is an odd integer. Considerably less is known about odd-distance graphs than unit-distance graphs. For example we don't know if there is an upper bound on the chromatic number or not. In this talk we show an infinite family of graphs that are not odd-distance graphs. 

    An n-wheel is a  graph formed by connecting a new vertex to all vertices of a cycle of length n. Piepemeyer showed that K_n,n,n, and therefore any 3-colorable graph, is an odd-distance graph. In particular the 2n-wheel is an odd distance graph for any n. On the other hand it is well known that the 3-wheel (K_4) is not an odd-distance graph, and Rosenfeld and Le showed that the 5-wheel is also not an odd-distance graph.  We show that the 2n+1-wheel is not an odd-distance graph for any n.