A graph is k-critical if every proper subgraph is (k-1)-colorable, but the graph itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least log n/(100 log k). Examples show the bound cannot be improved above 2(k-1)log n/log(k-2). This is joint work with A. Shapira.
Copyright. All Rights Reserved.