A strengthening on odd cycles in graphs of given chromatic number

Abstract

Resolving a conjecture of Bollobás and Erdős, Gyárfás proved that every graph $G$ of chromatic number $k+1\ge 3$ contains cycles of $\lfloor \frac{k}{2}\rfloor$ distinct odd lengths. We strengthen this prominent result by showing that such $G$ contains cycles of $\lfloor \frac{k}{2}\rfloor$ consecutive odd lengths. Along the way, combining extremal and structural tools, we prove a stronger statement that every graph of chromatic number $k+1\ge 7$ contains $k$ cycles of consecutive lengths, except that some block is $K_{k+1}$. As corollaries, this confirms a conjecture of Verstraëte and answers a question of Moore and West.

The proof of the cases k=3,4 for Theorem 1.3 is uploaded as an ancillary file

Cited by in corpus (1)

• A note on cycle lengths in graphs of chromatic number five and six