Graphs with girth 8 and without longer even holes are 3-colorable

Abstract

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