The circumference of colorcritical graphs
The circumference of colorcritical graphs

Robin Thomas, Georgia Institute of Technology
Fine Hall 224
A graph is kcritical if every proper subgraph is (k1)colorable, but the graph itself is not. We prove that every kcritical graph on n vertices has a cycle of length at least log n/(100 log k). Examples show the bound cannot be improved to exceed 2(k1)log n/log(k2). This is joint work with A. Shapira.