Graphs with girth $2\ell +1$ and without longer odd holes are $3$-colorable

Abstract

For a number $\ell \ge 2$, let ${\mathcal{G}}_{\ell }$ denote the family of graphs which have girth $2\ell +1$ and have no odd hole with length greater than $2\ell +1$. Plummer and Zha conjectured that every 3-connected and internally 4-connected graph in ${\mathcal{G}}_2$ is 3-colorable. Wu, Xu, and Xu conjectured that every graph in ${\bigcup }_{\ell \ge 2}{\mathcal{G}}_{\ell }$ is 3-colorable. Chudnovsky et al. and Wu et al., respectively, proved that every graph in ${\mathcal{G}}_2$ and ${\mathcal{G}}_3$ is 3-colorable. In this paper, we prove that every graph in ${\bigcup }_{\ell \ge 5}{\mathcal{G}}_{\ell }$ is 3-colorable.

arXiv admin note: text overlap with arXiv:2210.12376