Speaker: Dan Cranston, Virginia Commonwealth University

Title: Planar graphs are 9/2-colorable and have big independent sets

Abstract: 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
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491