Color-Critical Graphs Have Logarithmic Circumference

Series
Graph Theory Seminar
Time
Friday, October 30, 2009 - 3:05pm for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Asaf Shapira – Math and CS, GT
Organizer
Robin Thomas
A graph G is k-critical if every proper subgraph of G is (k-1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least logn/100logk, improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that this bound is tight (up to a constant depending on k). We thus settle the problem of bounding the minimal circumference of k-critical graphs, raised by Dirac in 1952 and Kelly and Kelly in 1954. This is joint work with Robin Thomas.