Graphs with girth 9 and without longer odd holes are 3-colorable

Abstract

For a number $l\ge 2$, let ${\mathcal{G}}_l$ denote the family of graphs which have girth $2l+1$ and have no odd hole with length greater than $2l+1$. Wu, Xu and Xu conjectured that every graph in ${\bigcup }_{l\ge 2}{\mathcal{G}}_l$ is $3$-colorable. Chudnovsky et al., Wu et al., and Chen showed that every graph in ${\mathcal{G}}_2$, ${\mathcal{G}}_3$ and ${\bigcup }_{l\ge 5}{\mathcal{G}}_l$ is $3$-colorable respectively. In this paper, we prove that every graph in ${\mathcal{G}}_4$ is $3$-colorable. This confirms Wu, Xu and Xu's conjecture.

arXiv admin note: substantial text overlap with arXiv:2210.12376, arXiv:2301.00112 by other authors