Cycles in triangle-free graphs of large chromatic number

Abstract

More than twenty years ago Erdős conjectured~\cite{E1} that a triangle-free graph $G$ of chromatic number $k\ge k_0(\epsilon )$ contains cycles of at least $k^{2-\epsilon }$ different lengths as $k\to \infty$. In this paper, we prove the stronger fact that every triangle-free graph $G$ of chromatic number $k\ge k_0(\epsilon )$ contains cycles of $(\frac{1}{64}-\epsilon )k^2\log k$ consecutive lengths, and a cycle of length at least $(\frac{1}{4}-\epsilon )k^2\log k$. As there exist triangle-free graphs of chromatic number $k$ with at most roughly $4k^2\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 $K_r$-free graphs and graphs without odd cycles $C_{2s+1}$.

10 pages

Cited by in corpus (1)

• Cycle lengths and minimum degree of graphs