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

Rong Chen ; Yidong Zhou

The electronic journal of combinatorics, Tome 31 (2024) no. 1

Résumé

We say that a graph $G$ has an 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\geq 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\geq2}\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\geq5}\mathcal{G}_{\ell}$ has an odd $K_4$-subdivision. Using this result, Chen proved that all graphs in $\bigcup_{\ell\geq5}\mathcal{G}_{\ell}$ are $3$-colorable.

Détail

DOI : 10.37236/12135

Classification : 05C15, 05C17, 05C69
Mots-clés : induced subgraph, pentagraph, \(k\)-colorable