Back to Search Start Over

Chi-boundedness of graphs containing no cycles with $k$ chords

Authors :
Lee, Joonkyung
Letzter, Shoham
Pokrovskiy, Alexey
Publication Year :
2022

Abstract

We prove that the family of graphs containing no cycle with exactly $k$-chords is $\chi$-bounded, for $k$ large enough or of form $\ell(\ell-2)$ with $\ell \ge 3$ an integer. This verifies (up to a finite number of values $k$) a conjecture of Aboulker and Bousquet (2015).<br />Comment: 38 pages, 13 figures

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2208.14860
Document Type :
Working Paper