Combinatorics Seminar
When: Sunday, December 20, 10am
Where: Schreiber 309
Speaker: Asaf Shapira, Georgia Institute of Technology
Title: Color-Critical Graphs Have Logarithmic
Circumference
Abstract:
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
a joint work with Robin Thomas.