DIMACS Discrete Mathematics Seminar


High Girth 4-Chromatic Unit Distance Graphs in the Plane


Paul Odonell
Rutgers University


CoRE Building Room 431
Busch Campus, Rutgers University


4:30 PM
Tuesday, March 21, 1995


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.
Document last modified on March 10, 1995