DIMACS Discrete Mathematics Seminar


Title:

High Girth 4-Chromatic Unit Distance Graphs in the Plane

Speaker:

Paul Odonell
Rutgers University

Place:

CoRE Building Room 431
Busch Campus, Rutgers University

Time:

4:30 PM
Tuesday, March 21, 1995

Abstract:

Two classes of fixed girth (9 and 12), arbitrary chromatic number will be constructed / shown to exist. Although constructions of *arbitrary* girth, arbitrary chromatic number graphs are known, these two classes of graphs have some interesting properties. Their structure is easy to describe and visualize, and a 4-chromatic graph from each class can be embedded as a unit distance graph in the Euclidean plane. The polynomial Szemeredi theorem of Bergelson and Leibman, and a theorem of Faltings are used to establish the girth and chromatic number of each of the graphs. The embeddings of the 4-chromatic graphs are relatively painless due to the simple structure of the graphs.
dimacs-www@dimacs.rutgers.edu
Document last modified on March 10, 1995