Graphs with girth 2ℓ+1 and without longer odd holes are 3-colorable

2022/12/31 by Chen, Rong · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2301.00112

Abstract

For a number ℓ≥ 2, let G_ℓ denote the family of graphs which have girth 2ℓ+1 and have no odd hole with length greater than 2ℓ+1. Plummer and Zha conjectured that every 3-connected and internally 4-connected graph in G₂ is 3-colorable. Wu, Xu, and Xu conjectured that every graph in \bigcup_ℓ≥2G_ℓ is 3-colorable. Chudnovsky et al. and Wu et al., respectively, proved that every graph in G₂ and G₃ is 3-colorable. In this paper, we prove that every graph in \bigcup_ℓ≥5G_ℓ is 3-colorable.

Cited by

• Graphs with girth 2ℓ and without longer even holes are 3-colorable

Related

• Graphs with girth 9 and without longer odd holes are 3-colorable
• Graphs with girth 2ℓ and without longer even holes are 3-colorable
• Graphs with girth 2ℓ+1 and without longer odd holes that contain an odd K₄-subdivision
• Coloring of graphs without long odd holes
• Graphs with large minimum degree and no small odd cycles are 3-colourable