Graphs with girth 2ℓ+1 and without longer odd holes that contain an odd K₄-subdivision

2022/10/22 by Rong Chen, Yidong Zhou, Chen, Rong +1
Computer Science · Mathematics · #05C15 #05C17 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2210.12376

openalex publication_date 2022/10/22 · openalex created_date 2022/10/31 · openalex updated_date 2026/07/28

Abstract

We say that a graph G has an \em odd K₄-subdivision if some subgraph of G is isomorphic to a K₄-subdivision and whose faces are all odd holes of G. 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. Wu, Xu and Xu conjectured that every graph in \bigcup_ℓ≥2G_ℓ is 3-colorable. Recently, 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 no 4-vertex-critical graph in \bigcup_ℓ≥5G_ℓ has an odd K₄-subdivision. Using this result, Chen proved that all graphs in \bigcup_ℓ≥5G_ℓ are 3-colorable.

Related

• 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
• Graphs with girth 2ℓ and without longer even holes are 3-colorable
• Coloring of graphs without long odd holes
• On coloring of graphs of girth 2l + 1 without longer odd holes