The circumference of color-critical graphs

Robin Thomas
Georgia Institute of Technology

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.

Back to Combinatorics Tutorials