Friday, September 13, 2013 — 3:30 PM to 4:30 PM EDT

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.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)