Graphs with large minimum degree and no small odd cycles are 3-colourable

2023/02/03 by Julia Böttcher, Böttcher, Julia, Nóra Frankl +6 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2302.01875

openalex publication_date 2023/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

Answering a question by Letzter and Snyder, we prove that for large enough k any n-vertex graph G with minimum degree at least (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.

Cited by

• A directed Andrásfai-Erdős-Sós theorem and chromatic profiles of oriented cycles

Related

• Improved algorithm to determine 3-colorability of graphs with the\n minimum degree at least 7
• Graphs with girth 9 and without longer odd holes are 3-colorable
• Graphs with girth 2ℓ+1 and without longer odd holes are 3-colorable
• On 3-colourability of (bull, H)-free graphs
• 3-colorability of graphs with minimum degree at least 6