Graphs with girth $2\ell +1$ and without longer odd holes that contain an odd $K_4$-subdivision

Abstract

We say that a graph $G$ has an {\em odd $K_4$-subdivision} if some subgraph of $G$ is isomorphic to a $K_4$-subdivision and whose faces are all odd holes of $G$. 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$. Wu, Xu and Xu conjectured that every graph in ${\bigcup }_{\ell \ge 2}{\mathcal{G}}_{\ell }$ is 3-colorable. Recently, 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 no $4$-vertex-critical graph in ${\bigcup }_{\ell \ge 5}{\mathcal{G}}_{\ell }$ has an odd $K_4$-subdivision. Using this result, Chen proved that all graphs in ${\bigcup }_{\ell \ge 5}{\mathcal{G}}_{\ell }$ are 3-colorable.

A figure of an odd $K_4$-subdivision was added