3-Coloring $P_t$-Free Graphs With Only One Prescribed Induced Odd Cycle Length

Abstract

A graph is $P_t$-free if it contains no induced subgraph isomorphic to a $t$-vertex path. A graph is not bipartite if and only if it contains an induced subgraph isomorphic to a $k$-vertex cycle, where $k$ is odd. We focus on the 3-coloring problem for $P_t$-free graphs that have only one prescribed induced odd cycle length. For any integer $t$ and any odd integer $k$, let ${\mathcal{G}}_{t,k}$ be the class of graphs that are $P_t$-free and all their induced odd cycles must be $C_k$. In this paper, we present a polynomial-time algorithm that solves the 3-coloring problem for any graph in ${\mathcal{G}}_{10,7}$.