Tight minimum degree condition to guarantee \(C_{2k+1}\)-free graphs to be \(r\)-partite

Abstract

Erd\H{o}s and Simonovits asked the following question: For an integer \(c\geq 2\) and a family of graphs \(\mathcal{F}\), what is the infimum of \(\alpha\) such that any \(\mathcal{F}\)-free \(n\)-vertex graph with 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 \cite{ES46, ES66} implies that for any \(c\le r-1\), \(\delta_{\chi}(\mathcal{F}, c)=1-{1 \over r}\), where \(r+1=\chi(\mathcal{F})=\min\{\chi (F): F\in \mathcal{F}\}\). 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 \(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 Nikiforov. In this paper, we focus on odd cycles. Combining results of Thomassen and Ma, we have \(\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\) (\(k\ge 5\) if \(c=2\)). We also obtain the following corollary. If \(G\) is a non-\(c\)-partite graph on \(n\) vertices with \(c\ge 3\) 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}]\).