Graphs with girth $2\ell$ and without longer even holes are $3$-colorable

Abstract

For a number $\ell \ge 2$, let ${\mathcal{H}}_{\ell }$ denote the family of graphs which have girth $2\ell$ and have no even hole with length greater than $2\ell$. Wu, Xu, and Xu conjectured that every graph in ${\bigcup }_{\ell \ge 2}{\mathcal{H}}_{\ell }$ is 3-colorable. In this paper, we prove that every graph in ${\mathcal{H}}_{\ell }$ is 3-colorable for any integer $\ell \ge 5$.

2 figures