Combinatorics Seminar

When: Sunday, January 4, 10am
Where: Schreiber 309
Speaker: Benny Sudakov, ETH Zurich
Title: Cycles in triangle-free graphs of large chromatic number


More than twenty years ago Erdős conjectured that a triangle-free graph G of chromatic number k contains cycles of at least k2-o(1) different lengths. In this talk we prove this conjecture in a stronger form, showing that every such G contains cycles of ck2log k consecutive lengths, which is tight. Our approach can be also used to give new bounds on the number of different cycle lengths for other monotone classes of k-chromatic graphs, i.e., clique-free graphs and graphs without odd cycles.

Joint work with A. Kostochka and J. Verstraete.