Department of
Applied
Mathematics

The Odd Distance Graph

Moshe Rosenfeld

University of Washington

Abstract

The unit distance graph is the infinite graph whose vertices are the points of the plane R^2, two vertices connected by an edge if their Euclidean distance is 1. This graph was introduced by Ed Nelson in 1950. It was established in 1950 that the chromatic number $\chi(G)$ of this graph is between 4 and 7. In spite of many attempts, these bounds have not been improved. I introduced the odd distance graph in 1994. Similarly, its vertices are the points in R^2, with two vertices connected by an edge if their Euclidean distance is an odd integer. How different is it from the unit distance graph? In this talk I will describe how different it is, what we know about it and and what we do not know (a lot ...).