Coloring graphs with two odd cycle lengths

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\ge 2$, then $\ddot{I}‡(G)=\max \{3,\ddot{I}‰(G)\}$; (2) If $L(G)=\{k,k+2l\}$, where $k\ge 5$ and $l\ge 1$, then $\ddot{I}‡(G)=3$. These, together with the case $L(G)=\{3,5\}$ solved in \cite{W}, give a complete solution to the general problem addressed in \cite{W,CS,KRS}. Our results also improve a classical theorem of Gyárfás which asserts that $\ddot{I}‡(G)\le 2|L(G)|+2$ for any graph $G$.

26 pages,accepted version for publication in SIAM J. Discrete Math