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

Series
Graph Theory Seminar
Time
Thursday, September 2, 2010 - 12:05pm for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Luke Postle – Math, GT
Organizer
Robin Thomas
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.