Odd and even cycle lengths, minimum degree and chromatic number in graphs

In this paper, we prove similar results for odd and even cycle lengths. Let $L_o(G)$ denote the set of odd cycle lengths of $G$ and ${\mathrm{\ell }}_o(G)$ denote the longest odd cycle length. In 1992, Gyárfás proved that $\chi (G)\le 2\mathrm{\mid }{L}_o(G)\mathrm{\mid }+2$, and if $w(G)\le 2\mathrm{\mid }{L}_o(G)\mathrm{\mid }+1$, then $\chi (G)\le 2\mathrm{\mid }{L}_o(G)\mathrm{\mid }+1$. We first prove that if $G$ is a 2-connected non-bipartite graph with $\delta (G)\ge 2k$, then $\mathrm{\mid }{L}_o(G)\mathrm{\mid }\ge k$. Moreover, if $\mathrm{\mid }{L}_o(G)\mathrm{\mid }=k$, then $2\mathrm{\mid }{L}_o(G)\mathrm{\mid }+1={\mathrm{\ell }}_o(G)$, and either $K_{2k+1}\subseteq G$ or $\chi (G)\le 2k$. Applying this result, we prove that if $w(G)\le 2\mathrm{\mid }{L}_o(G)\mathrm{\mid }$, then $\chi (G)\le 2\mathrm{\mid }{L}_o(G)\mathrm{\mid }$ for $\mathrm{\mid }{L}_o(G)\mathrm{\mid }\ge 2$, improving the result of Gyárfás. We also construct a class of graphs with $w(G)=2\mathrm{\mid }{L}_o(G)\mathrm{\mid }-1$ but $\chi (G)=2\mathrm{\mid }{L}_o(G)\mathrm{\mid }$ for every $\mathrm{\mid }{L}_o(G)\mathrm{\mid }\ge 2$. Using our result, we give a short proof of a similar result of $\chi (G)$ and ${\mathrm{\ell }}_o(G)$ proved by Kenkre and Vishwanathan. Our second part is about even cycle lengths. Let $L_e(G)$ denote the set of even cycle lengths of $G$ and ${\mathrm{\ell }}_e(G)$ denote the longest even cycle length. In 2004, Mihók and Schiermeyer proved that $\chi (G)\le 2\mathrm{\mid }{L}_e(G)\mathrm{\mid }+3$, and if $w(G)\le 2\mathrm{\mid }{L}_e(G)\mathrm{\mid }+2$, then $\chi (G)\le 2\mathrm{\mid }{L}_e(G)\mathrm{\mid }+2$. We first prove that if $G$ is a 2-connected graph with $\delta (G)\ge 2k+1$, then $\mathrm{\mid }{L}_e(G)\mathrm{\mid }\ge k$. Moreover, if $\mathrm{\mid }{L}_e(G)\mathrm{\mid }=k$, then $2\mathrm{\mid }{L}_e(G)\mathrm{\mid }+2={\mathrm{\ell }}_e(G)$, and either $K_{2k+2}\subseteq G$ or $\chi (G)\le 2k+1$. Applying this result, we prove that if $w(G)\le 2\mathrm{\mid }{L}_e(G)\mathrm{\mid }+1$, then $\chi (G)\le 2\mathrm{\mid }{L}_e(G)\mathrm{\mid }+1$ for $\mathrm{\mid }{L}_e(G)\mathrm{\mid }\ge 2$, improving the result of Mihók and Schiermeyer. We also construct a class of graphs with $w(G)=2\mathrm{\mid }{L}_e(G)\mathrm{\mid }$ but $\chi (G)=2\mathrm{\mid }{L}_e(G)\mathrm{\mid }+1$ for every $\mathrm{\mid }{L}_e(G)\mathrm{\mid }\ge 2$. Our result can deduce a similar result of $\chi (G)$ and ${\mathrm{\ell }}_e(G)$. The above results also improve some results of consecutive odd or even cycle lengths.