Colloquium

Title: Planar graphs are 9/2-colorable and have independence ratio at least 3/13

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 9/2 Color Theorem, which we can prove by hand.

A 2-fold coloring assigns to each vertex 2 colors, such that adjacent vertices get disjoint sets of colors. We show that every planar graph G has a 2-fold 9-coloring. In particular, this implies that G has fractional chromatic number at most 9/2. This is the first proof (independent of the 4 Color Theorem) that there exists a constant k<5 such that every planar G has fractional chromatic number at most k. We also show that every n-vertex planar graph has an independent set of size at least 3n/13. This improves on Albertson's bound of 2n/9, which was the best result independent of the 4 Color Theorem.

This is joint work with Landon Rabern.

Short Bio: Daniel Cranston earned his PhD in 2007 from University of Illinois, under the direction of Douglas West. From September 2007 to August 2009, Cranston was a postdoctoral fellow at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) and Bell Labs, Rutgers University and Murray Hill, NJ. Cranston is currently assistant professor in the Department of Mathematics and Applied Mathematics at Virginia Commonwealth University. His research interests are mainly in graph theory and algorithms, but he is also interested in most areas of discrete math. He has been awarded NSA Young Investigator’s Award for the next academic year.