W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Mathematics Colloquium Talk
March 20, 2015
2pm - 3pm
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 less than 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.
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 less than 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.
Contact
Professor Gexin Yu, Department of Mathematics