MATH Seminar

Title: 5-Coloring Graphs on Surfaces
Seminar: Combinatorics
Speaker: Luke Postle of Georgia Institute of Technology
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2012-01-25 at 3:00PM
Venue: W306
Download Flyer
Abstract: Graph coloring is a much studied subfield of graph theory. Theorems concerning coloring graphs on topological surfaces, such as the Four Color Theorem or the Heawood Bound, are a useful avenue to understanding graph coloring in general. A deep theorem of Thomassen from the 1990's shows that for any surface that there are only finitely many 6-critical graphs that embed on that surface. We discuss the history of this modern approach and its realisation for small surfaces. We also give a shorter self-contained proof of Thomassen's result by showing that for any 6-critical graph G that embeds on a surface of genus $g$, that the number of vertices is at most linear in $g$. Finally, we discuss generalizations to 5-list coloring,such as a recent solution to Albertson's conjecture that a planar graph with distant precolored vertices has a 5-list-coloring.