Graphs with large minimum degree and no short odd cycles are \(3\)-colourable
Combinatorial Theory · 2026
DOI: 10.5070/c6.69944 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorial Theory, 2026. Verfasst von Julia Böttcher und 4 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Answering a question by Letzter and Snyder, we prove that for large enough \(k\), any \(n\)-vertex graph \(G\) with minimum degree at least \(\frac{1}{2k-1}n\) and without odd cycles of length less than \(2k+1\) is \(3\)-colourable. In fact, we prove a stronger result that works with a slightly smaller minimum degree. Mathematics Subject Classifications: 05C35, 05C15 Keywords: Chromatic profile, Minimum degree, Graph colouring
Zitieren
APA
Böttcher, J., Frankl, N., Cecchelli, D. M., Parczyk, O., & Skokan, J. (2026). Graphs with large minimum degree and no short odd cycles are \(3\)-colourable. Combinatorial Theory. https://doi.org/10.5070/c6.69944
Vancouver
Böttcher J, Frankl N, Cecchelli DM, Parczyk O, Skokan J. Graphs with large minimum degree and no short odd cycles are \(3\)-colourable. Combinatorial Theory. 2026. doi:10.5070/c6.69944
BibTeX
@article{Bttcher2026,
author = {Böttcher, Julia and Frankl, Nóra and Cecchelli, Domenico Mergoni and Parczyk, Olaf and Skokan, Jozef},
title = {Graphs with large minimum degree and no short odd cycles are \(3\)-colourable},
journal = {Combinatorial Theory},
year = {2026},
doi = {10.5070/c6.69944}
}
EUVIMED