# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | future lectures)

On 03.05.2012 at 12:20 in S6, there is the following noon lecture:

# 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.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | future lectures)

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010