Chromatic profiles of odd cycles

Abstract

Erdős and Simonovits asked the following question: For an integer $c\ge 2$ and a family of non-bipartite graphs $\mathcal{F}$, what is the infimum of $\hat{I}\pm$ such that any $\mathcal{F}$-free $n$-vertex graph with $n$ large enough and minimum degree at least $\hat{I}\pm n$ has chromatic number at most $c$? Denote the infimum as $\hat{I}{´}_{\ddot{I}}‡(\mathcal{F},c)$. A fundamental result of Erdős, Stone and Simonovits implies that if $3\le r+1=\ddot{I}‡(\mathcal{F})=\min \{\ddot{I}‡(F):F\in \mathcal{F}\}$, then for any $c\le r-1$, $\hat{I}{´}_{\ddot{I}}‡(\mathcal{F},c)=1-\frac{1}{r}$. So the remaining challenge is to determine $\hat{I}{´}_{\ddot{I}}‡(\mathcal{F},c)$ for $c\ge \ddot{I}‡(\mathcal{F})-1$. Most previous known results are under the condition that $c=\ddot{I}‡(\mathcal{F})-1$. When $c\ge \ddot{I}‡(\mathcal{F})$, the only known exact results are $\hat{I}{´}_{\ddot{I}}‡(K_3,3)$ by Häggkvist and Jin, and $\hat{I}{´}_{\ddot{I}}‡(K_3,c)$ for every $c\ge 4$ by Brandt and Thomassé, $\hat{I}{´}_{\ddot{I}}‡(K_r,r)$ and $\hat{I}{´}_{\ddot{I}}‡(K_r,r+1)$ by Goddard and Lyle, and Nikiforov. Combining results of Thomassen and Ma, $\hat{I}\text{c◯}((c+1{)}^{-8(k+1)})=\hat{I}{´}_{\ddot{I}}‡(C_{2k+1},c)=O(\frac{k}{c})$ for $c\ge 3$. In this paper, we determine $\hat{I}{´}_{\ddot{I}}‡(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$, $\ddot{I}‡(G)>c$ and $\hat{I}´(G)>\frac{n}{2c+2}$, then $C_{2k+1}\subset G$ for all $k\in [3c+4,\frac{n}{108(c+1{)}^c}]$. Methods to obtain all previous known results related to odd cycles cannot be applied to solve for $\hat{I}{´}_{\ddot{I}}‡(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.

arXiv admin note: text overlap with arXiv:2408.15487