Answers are grounded in this paper and cite their sources.
We say that a graph G has an 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 ≥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 ≥5G_ has an odd K₄-subdivision. Using this result, Chen proved that all graphs in ≥5G_ are $3$-colorable.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: