EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Graphs with large minimum degree and no short odd cycles are \(3\)-colourable

Julia Böttcher, Nóra Frankl, Domenico Mergoni Cecchelli, Olaf Parczyk, Jozef Skokan

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →