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