Erd\H{ o}s and Simonovits asked the following question: For an integer $c\geq 2$ and a family of non-bipartite graphs $\mathcal{ F}$, what is the infimum of $\alpha$ such that any $\mathcal{ F}$-free $n$-vertex graph with $n$ large enough and minimum degree at least $\alpha n$ has chromatic number at most $c$? Denote the infimum as $\delta_{ \chi}(\mathcal{ F}, c)$. A fundamental result of Erd\H{ o}s, Stone and Simonovits implies that if $3\le r+1=\chi(\mathcal{ F})=\min\{ \chi (F): F\in \mathcal{ F}\}$, then for any $c\le r-1$, $\delta_{ \chi}(\mathcal{ F}, c)=1-{ 1 \over r}$. So the remaining challenge is to determine $\delta_{ \chi}(\mathcal{ F}, c)$ for $c\ge \chi (\mathcal{ F})-1$. Most previous known results are under the condition that $c= \chi (\mathcal{ F})-1$. When $c\ge \chi (\mathcal{ F})$, the only known exact results are $\delta_{ \chi}(K_3, 3)$ by H\"aggkvist and Jin, and $\delta_{ \chi}(K_3, c)$ for every $c\ge4$ by Brandt and Thomass\'{ e}, $\delta_{ \chi}(K_r, r)$ and $\delta_{ \chi}(K_r, r+1)$ by Goddard and Lyle, and Nikiforov. Combining results of Thomassen and Ma, $\Omega\bigg((c+1)^{ -8(k+1)}\bigg)=\delta_{ \chi}(C_{ 2k+1}, c)=O(\frac{ k}{ c})$ for $c\ge 3$. In this paper, we determine $\delta_{ \chi}(C_{ 2k+1}, c)$ for all $c\ge 2$ and $k\ge 3c+4$. We also obtain the following corollary. If $G$ is a graph on $n$ vertices with $c\ge 3$, $\chi(G)>c$ and $\delta(G)> { n \over 2c+2}$, then $C_{ 2k+1} \subset G$ for all $k\in [3c+4, { n \over 108(c+1)^c}]$. Methods to obtain all previous known results related to odd cycles cannot be applied to solve for $\delta_{ \chi}(C_{ 2k+1}, c)$ for $c\ge 3$.The innovation of our proof is to give the concept of a `strong $2k$-core'. We think that this concept grasps the essence of the problem and it makes our proof concise and elementary (we do not need to borrow any other tools). How to define a proper `core' might be a key to this type of questions.
Categories: math.CO