Cycles in triangle-free graphs of large chromatic number

More than twenty years ago Erdős conjectured [4] that a triangle-free graph G of chromatic number k≥k₀(ε) contains cycles of at least k^2−ε different lengths as k→∞. In this paper, we prove the stronger fact that every triangle-free graph G of chromatic number k≥k₀(ε) contains cycles of 1/64(1 − ε)k² logk/4 consecutive lengths, and a cycle of length at least 1/4(1 − ε)k²logk. As there exist triangle-free graphs of chromatic number k with at most roughly 4k² logk vertices for large k, these results are tight up to a constant factor. We also give new lower bounds on the circumference and the number of different cycle lengths for k-chromatic graphs in other monotone classes, in particular, for K_r-free graphs and graphs without odd cycles C_2s+1.