Structure and Colour in Triangle-Free Graphs

Aravind, N. R. and Cambie, Stijn and Cames van Batenburg, Wouter and De Joannis de Verclos, Rémi and Kang, Ross J. and Patel, Viresh (2021) Structure and Colour in Triangle-Free Graphs. The Electronic Journal of Combinatorics, 28 (2). ISSN 1077-8926

Full text not available from this repository. (Request a copy)


Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number χ contains a rainbow independent set of size ⌈12χ⌉. 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 χ contains an induced cycle of length Ω(χ log χ) as χ → ∞. Even if one only demands an induced path of length Ω(χ log χ), 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 cD/ log D. We prove this assertion with ‘triangle-free’ replaced by ‘regular girth 5’.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Aravind, N R
Item Type: Article
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 30 Jul 2021 04:05
Last Modified: 07 Mar 2022 06:14
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8566 Statistics for this ePrint Item