The Odd-Distance Graph

Moshe Rosenfeld

University of Washington Tacoma

Abstract

Joint work with Hayri Ardal, Jano Manuch, Ladislav Stacho (SFU), Saharon Shelah (HUJI), Le Tieng Nam (Vietnam National University, Hanoi).

The Odd-Distance Graph is a close relative of Nelson's famous Unit-Distance Graph. It's vertices are the points in the plane R^2 with edges between points whose distance is an odd integer. This graph does not contain K_4 as a subgraph, which led to the natural question: what is the chromatic number of this graph?

The Odd-Distance Graph was "exposed" by Paul Erdos (who else?) in 1994 in his traditional talk at the Boca Raton, Florida conference. In this talk I will discusss the current known facts and open problems:

1. Its chromatic number is at least five 2. Its "local" density (maximum number of edges in finite subgraphs). 3. List chromatic number is \aleph_0 4. List chromatic number of the Odd-Distance Graph in R^3 is > \aleph_0. 5.