Coloring Graphs with Two Odd Cycle Lengths

Source abstract

In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let $G$ be a graph and $L(G)$ be the set of all odd cycle lengths of $G$. We prove that (1) if $L(G)=\{3,3+2l\}$, where $l\geq 2$, then $\chi(G)=\max\{3,\omega(G)\}$, and (2) if $L(G)=\{k,k+2l\}$, where $k\geq 5$ and $l\geq 1$, then $\chi(G)=3$. These, together with the case $L(G)=\{3,5\}$ solved in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040--1072] give a complete solution to the general problem addressed in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040--1072; S.-M. Camacho and I. Schiermeyer, Discrete Math., 309 (2009), pp. 4916--4919; and T. Kaiser, O. Rucký, and R. Škrekovski, SIAM J. Discrete Math., 25 (2011), pp. 1069--1088]. Our results also improve a classical theorem of Gyárfás which asserts that $\chi(G)\le 2|L(G)|+2$ for any graph $G$.