On coloring of graphs of girth 2l + 1 without longer odd holes

Abstract

A hole is an induced cycle of length at least 4. Let $ł\ge 2$ be a positive integer, let ${\mathcal{G}}_l$ denote the family of graphs which have girth $2ł+1$ and have no holes of odd length at least $2ł+3$, and let $G\in {\mathcal{G}}_{ł}$. For a vertex $u\in V(G)$ and a nonempty set $S\subseteq V(G)$, let $d(u,S)=\min \{d(u,v):v\in S\}$, and let $L_i(S)=\{u\in V(G) \mbox{ and } d(u, S)=i\}$ for any integer $i\ge 0$. We show that if $G[S]$ is connected and $G[L_i(S)]$ is bipartite for each $i\in \{1,\dots ,\lfloor \frac{ł}{2}\rfloor \}$, then $G[L_i(S)]$ is bipartite for each $i>0$, and consequently $\chi (G)\le 4$, where $G[S]$ denotes the subgraph induced by $S$. Let ${\theta }^{-}$ be the graph obtained from the Petersen graph by deleting three vertices which induce a path, let ${\theta }^{+}$ be the graph obtained from the Petersen graph by deleting two adjacent vertices, and let $\theta$ be the graph obtained from ${\theta }^{+}$ by removing an edge incident with two vertices of degree 3. For a graph $G\in {\mathcal{G}}_2$, we show that if $G$ is 3-connected and has no unstable 3-cutset then $G$ must induce either $\theta$ or ${\theta }^{-}$ but does not induce ${\theta }^{+}$. As corollaries, $\chi (G)\le 3$ for every graph $G$ of ${\mathcal{G}}_2$ that induces neither $\theta$ nor ${\theta }^{-}$, and minimal non-3-colorable graphs of ${\mathcal{G}}_2$ induce no ${\theta }^{+}$.