- 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.