MATH Seminar
| Title: 3-Coloring and 3-List-Coloring Graphs on Surfaces |
|---|
| Seminar: Combinatorics |
| Speaker: Luke Postle of Emory University |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2013-11-22 at 4:00PM |
| Venue: W306 |
| Download Flyer |
| 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. |
See All Seminars