On 03.05.2012 at 12:20 in S6, there is the following noon lecture:
The Odd-Distance Graph
University of Washington Tacoma
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. K_4 is not the only "forbidden" subgraph of the Odd-Distance Graph.
Modified: 19. 10. 2010