|
Session 27. Probabilistic and Extremal Combinatorics
|
Cycles in triangle-free graphs of large chromatic number |
Benny Sudakov, ETH Zürich, Switzerland
|
The talk is based on the joint work with Alexandr Kostochka and Jacques Verstraete
|
|
|
More than twenty years ago Erdős conjectured that a triangle-free graph \(G\) of chromatic number \(k \geq k_0(\varepsilon)\) contains cycles of at least \(k^{2 - \varepsilon}\) different lengths as \(k \rightarrow \infty\). In this paper, we prove the stronger fact that every triangle-free graph \(G\) of chromatic number \(k \geq k_0(\varepsilon)\) contains cycles of \((\frac{1}{64} - \varepsilon)k^2 \log k\) consecutive lengths, and a cycle of length at least \((\tfrac{1}{4} - \varepsilon)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 clique-free graphs and graphs without odd cycles.
|
|
| Print version |
|
