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

Abstract

We present the relations between clique number and chromatic number with given the number of odd or even or all cycle lengths. Let $L_o(G)$ be the set of odd cycle lengths of $G$ and ${\ell }_o(G)$ be the longest odd cycle length. Gyárfás (DM, 1992) proved a classic result: $\chi (G)\le 2|L_o(G)|+2$, and if $w(G)\le 2|L_o(G)|+1$, then $\chi (G)\le 2|L_o(G)|+1$. Later, Wang (SIAM DM, 2008), Ma and Ning (SIAM DM, 2018) together determined the exact chromatic number when $|L_o(G)|=2$. We further prove that if $w(G)\le 2|L_o(G)|$ for any $|L_o(G)|\ge 2$, then $\chi (G)\le 2|L_o(G)|$. We also construct a class of graphs with $w(G)=2|L_o(G)|-1$ but $\chi (G)=2|L_o(G)|$ for every $|L_o(G)|\ge 2$. Using our result, we give a short proof of the relation between $w(G)$ and $\chi (G)$ with given ${\ell }_o(G)$ proved by Kenkre and Vishwanathan (JGT, 2006). Let $L_e(G)$ be the set of even cycle lengths of $G$ and ${\ell }_e(G)$ be the longest even cycle length. Mihók and Schiermeyer (DM, 2004) proved that $\chi (G)\le 2|L_e(G)|+3$, and if $w(G)\le 2|L_e(G)|+2$, then $\chi (G)\le 2|L_e(G)|+2$. We further prove that if $w(G)\le 2|L_e(G)|+1$ and $|L_e(G)|\ge 3$, then $\chi (G)\le 2|L_e(G)|+1$. We also construct a class of graphs with $w(G)=2|L_e(G)|$ but $\chi (G)=2|L_e(G)|+1$ for every $|L_e(G)|\ge 2$. Our result can deduce the relation between $w(G)$ and $\chi (G)$ with given ${\ell }_e(G)$. Combining all the above results, we deduce the similar relations between $w(G)$ and $\chi (G)$ with given the number of cycle lengths or the longest cycle length.