Skip to main content
Graphs with large minimum degree and no short odd cycles are \(3\)-colourable
Published Web Location
https://doi.org/10.5070/C6.69944Abstract
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