3-Coloring and 3-List-Coloring Graphs of Girth at least Five on Surfaces
| Speaker: | Luke Postle |
|---|---|
| Affiliation: | University of Waterloo and Emory University |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
Grotzsch proved that every triangle-free planar graph is 3-colorable. This theorem follows easily once one proves that every planar graph of girth at least five is 3-colorable. There are now three short proofs of this using three different methods: discharging, list-coloring, and the new potential technique of Kostochka and Yancey.
It is natural to wonder how this can be generalized to surfaces; for example whether locally planar graphs of girth at least five are 3-colorable or whether there exists a polynomial-time algorithm to decide 3-coloring on a fixed surface. Both of these results are implied by the following more general result of Thomassen: For every surface, there exist only finitely many 4-critical graphs of girth at least five embeddable on that surface.
Dvorak, Kral and Thomas provided a discharging proof of Thomassen's theorem to prove a stronger result that the number of vertices in such graphs is linear in genus. This was a needed ingredient in their proof of Havel's conjecture which states that a planar graph with triangles far apart is 3-colorable. We will discuss two new proofs of this linear bound result, one using list-coloring and one using the potential technique, and their various corollaries, such as the generalization of Thomassen's theorem to 3-list-coloring.