The number of vertices in a 6-critical graph is linear in its genus

Graph Theory Seminar
Thursday, September 2, 2010 - 12:05
1 hour (actually 50 minutes)
Skiles 114
Math, GT
A deep theorem of Thomassen shows that for any surface there are only finitely many 6-critical graphs that embed on that surface. We give a shorter self-contained proof that for any 6-critical graph G that embeds on a surface of genus g, that |V(G)| is at most linear in g. Joint work with Robin Thomas.