Structure and colour in triangle-free graphs

N. R. Aravind ; Stijn Cambie ; Wouter Cames van Batenburg ; Rémi de Joannis de Verclos ; Ross J. Kang¹ ; Viresh Patel

¹Radboud University Nijmegen

The electronic journal of combinatorics, Tome 28 (2021) no. 2

Résumé

Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $\chi$ contains a rainbow independent set of size $\lceil\frac12\chi\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $\chi$ contains an induced cycle of length $\Omega(\chi\log\chi)$ as $\chi\to\infty$. Even if one only demands an induced path of length $\Omega(\chi\log\chi)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $c D/\log D$. We prove this assertion with 'triangle-free' replaced by 'regular girth 5'.

Détail

DOI : 10.37236/9267

Classification : 05C15, 05C12
Mots-clés : Johansson's theorem, chromatic number