Combinatorics Seminar

When: Sunday, May 25, 10am

Where: Schreiber 309

Speaker: Moshe Rosenfeld, Seattle

Title: The odd-distance graph


metric graphs or distance graphs are graphs G(M;D) where M is a subset of a metric space and D is a set of positive numbers; two vertices are connected by an edge if their distance lies in D. One of the most famous distance graphs is the unit distance graph G(R^2;{1}). Two "close" relatives are the integral distance graph G(R^2;Z+) and the odd distance graph G(R^2; {2n + 1, n = 1, 2,.. }). The odd distance graph was "launched" in 1994 by Paul Erdos. At the outset, we wondered how close are the unit distance graph and the odd distance graph, we now know that they are very far apart. In this talk I will discuss the latest results in the pursuit of uncovering the mysteries of the odd distance graph:
  1. Its chromatic number is at least 5, no upper bound is known.
  2. Its List chromatic number is Aleph_0
  3. Forbidden subgraphs.
  4. Faithful embedding of 3-colorable graphs.
  5. Faithful embeddings of infinite graphs.
  6. An ever growing list of related open problems.
w3c valid   accessible website
redesigned by barak soreq