# 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