2014/04/17 by Kostochka, Alexandr, Sudakov, Benny, Verstraete, Jacques
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1404.4544
More than twenty years ago Erdős conjectured~\citeE1 that a triangle-free graph G of chromatic number k ≥ k0(ε) contains cycles of at least k2 - ε different lengths as k → ∞. In this paper, we prove the stronger fact that every triangle-free graph G of chromatic number k ≥ k0(ε) contains cycles of ((1)/(64) - ε)k2 log k consecutive lengths, and a cycle of length at least (\tfrac14 - ε)k2 log k. As there exist triangle-free graphs of chromatic number k with at most roughly 4k2 log k vertices for large k, theses 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 Kr-free graphs and graphs without odd cycles C2s+1.