James Bailey, Ph.D.

he/him

Education: Bachelor of Science in industrial engineering and mathematics (May 2012)

Master of Science in industrial engineering from Kansas State University

Doctor of Philosophy in algorithms, combinatorics, and optimization from the Georgia Institute of Technology

McNair Project: An Intermediate Perfect Graph Theorem (2011)

Mentor: Todd Easton, Ph.D.

A graph is perfect if for every induced subgraph H, the chromatic number of H is equal to the size of the largest clique in H. The strong perfect graph theorem states that a graph is perfect if and only if it contains no odd holes or odd anti-holes. To date there does not exist an elegant and easily verifiable proof of this theorem. This paper shows that a graph is perfect if it contains no odd holes and any odd cycles of length five have at least two chords.