Dan Cranston, Virginia Commonwealth University
Title: Planar graphs are 9/2-colorable and have big independent sets
For nearly a century, one of the major open questions in graph theory
was the Four Color Conjecture: Every planar graph can be properly
colored with four colors. In 1976, this conjecture was resolved (in
the affirmative) by Appel and Haken. Their result is called the 4
Color Theorem. Unfortunately, their proof (as well as later proofs of
this theorem) relies heavily on computers. In contrast, the 5 Color
Theorem is easy to prove. In this talk we look at a $\frac92$ Color
Theorem, which we can prove by hand.
This is joint work with Landon Rabern.
Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
Tel. 703-993-1460, Fax. 703-993-1491