Tight minimum degree condition to guarantee $C_{2k+1}$-free graphs to be $r$-partite
Zilong Yan Yuejian Peng Xiaoli Yuan





Tight minimum degree condition to guarantee C_2k+1-free graphs to be r-partite
     Zilong Yan [School of Mathematics, Hunan University,
 Changsha 410082, P. R. China. E-mail: zilongyan@hnu.edu.cn.]      Yuejian Peng [Corresponding author. School of Mathematics, Hunan University, Changsha 410082, P. R. China. E-mail: ypeng1@hnu.edu.cn. Supported in part by National Natural Science Foundation of China (No. 11931002)]        Xiaoli Yuan [School of Mathematics, Hunan University,
 Changsha 410082, P. R. China. E-mail: xiaoliyuan@hnu.edu.cn.] 


    
===================================================================================================================================================================================================================================================================================================================================================================================================================================================================================

§ ABSTRACT 
Erdős and Simonovits  asked the following question: For an integer c≥ 2 and a family of  graphs ℱ, what is the infimum of α such that any ℱ-free n-vertex graph with minimum degree at least α n has chromatic number at most c? Denote the infimum as δ_χ(ℱ, c).  A fundamental  result of
 Erdős, Stone and Simonovits <cit.> implies that for any c≤ r-1,
δ_χ(ℱ, c)=1-1  r, where r+1=χ(ℱ)=min{χ (F): F∈ℱ}.  So the remaining challenge is to determine δ_χ(ℱ, c) for c≥χ (ℱ)-1. Most previous known results are under the condition c= χ (ℱ)-1.  When c≥χ (ℱ), the only known exact results are  δ_χ(K_3, 3) by Häggkvist  and Jin, and δ_χ(K_3, c) for every c≥4 by Brandt and Thomassé, δ_χ(K_r, r) and δ_χ(K_r, r+1) by Nikiforov. In this paper, we focus on odd cycles. Combining results of Thomassen and Ma, we have  Ω((c+1)^-8(k+1))=δ_χ(C_2k+1, c)=O(k/c) for c≥ 3.  In this paper, we determine δ_χ(C_2k+1, c) for all c≥ 2 and k≥ 3c+4 (k≥ 5 if c=2). We also obtain the following corollary. If G is a non-c-partite graph on n vertices with c≥ 3 and δ(G)> n  2c+2, then C_2k+1⊂ G for all k∈ [3c+4, n  108(c+1)^c]. 




Keywords: minimum degree; odd cycle; chromatic profile, stability, Turán number.


§ INTRODUCTION

For  a graph G, V(G) and E(G) denote the vertex set and the edge set of G respectively.
Denote the minimum degree and the chromatic number of a graph G as δ(G) and  χ(G) respectively. For a   graph  F, what is the minimum  f(n, F) such that a graph G on n≥| V(F)| vertices with the minimum degree δ(G)≥ f(n, F) must contain a copy of F?
This question has had a long history (for example, well-known Dirac Theorem) and has always attracted a lot of attentions and has stimulated the development of graph theory. For example, the existence of cycles in graphs with sufficiently large minimum degree has been intensively studied (see <cit.>). In  an influential paper, Erdős and Simonovits <cit.> asked what happens if we know some information on the chromatic number χ(G). Precisely, for a  graph F and a positive integer c, what is the minimum  f(n, F, c) such that a graph G on n vertices with minimum degree δ(G)≥ f(n, F, c) and χ(G)>c must contain a copy of F?
This question has been stimulating the general study of the so-called chromatic profile. Let us define it below.

Let ℱ be a family of  graphs, a  graph G is ℱ-free if G does not contain any member of ℱ as a subgraph.  Call ℱ non-degenerate if χ(F)>2 for each F∈ℱ. 
For  a positive integer c≥ 2, the chromatic profile of a non-degenerate family ℱ as a function in c is defined to be

    δ_χ(ℱ, c)=inf{α| Any ℱ-free graph G  on n  vertices with δ(G)≥α n  must satisfy χ(G)≤ c.}.

 If ℱ consists of a single graph F, we simply write δ_χ({F}, c) as δ_χ(F, c), and write {F}-free as F-free.

 The study of chromatic profile is also related to the stability of Turán problems. For  a family ℱ of k-uniform graphs and a positive integer n, the Turán number ex(n, ℱ) is the maximum number of edges  an ℱ-free k-uniform graph on n vertices can have.    An averaging argument of Katona, Nemetz and Simonovits <cit.> shows that the sequence ex(n,ℱ) n  k is  non-increasing. Hence n→∞limex(n, ℱ) n  k exists. The Turán density of ℱ is defined as π(ℱ)=n→∞limex(n, ℱ) n  k .
If ℱ consists of a single k-uniform graph F, we simply write ex(n, {F}) and π({F}) as ex(n, F) and π(F). Let K_r+1 be the complete graph on r+1 vertices.
   Let T_r(n) denote the complete r-partite graph on n vertices where
 its part sizes are as equal as possible.
Turán <cit.>   obtained that if G is a K_r+1-free graph on n vertices,
then e(G)≤ e(T_r(n)), equality holds if and only if G=T_r(n).
  A fundamental  result of
 Erdős, Stone and Simonovits <cit.> gives the asymptotical value of ex(n, ℱ) for all non-degenerate families of graphs. For a family ℱ of graphs, let χ(ℱ)=min{χ (F): F∈ℱ}.


  
If ℱ is a family of graphs with
χ (ℱ)=r+1, then

    ex(n,ℱ) =e(T_r(n)) + o(n^2)= (  1-1/r + o(1)) n^2/2.


Erdős <cit.> and Simonovits <cit.> also obtained
a stronger structural  theorem of Theorem <ref> and
discovered  a certain stability phenomenon.



 
Let ℱ be a family of graphs with
χ (ℱ)=r+1≥ 3.
For every ε >0,
there exist δ >0 and n_0 such that
if G is a graph on n≥ n_0 vertices,
 and G is ℱ-free such that
e(G)≥ (1- 1/r - δ) n^2/2,
 then  G can be obtained from T_r(n)
by adding or deleting a total number of at most ε n^2 edges.


 Liu,  Mubayi and Reiher <cit.> also defined the degree-stability of Turán problems for k-uniform graphs which implies the edge-stability (as in Theorem <ref>).
Let ℱ be a non-degenerate family of k-uniform graphs (i.e. π(ℱ)>0). Let 𝒦 be a class of ℱ-free k-uniform graphs. If there exists ϵ >0 and n_0 such that every ℱ-free k-uniform graph G on n≥ n_0 vertices with δ(G)≥ (π(ℱ)-ϵ)n  k-1 is a subgraph of some member of 𝒦, then we say that ℱ is degree-stable with respect to 𝒦. It is not hard to see that the degree-stability implies the edge-stability (as in Theorem <ref>) since we can delete vertices with `small' degrees by losing o(n^k-1) edges.

If ℱ is a family of graphs with
χ (ℱ)=r+1≥ 3, then by Theorem <ref>, any ℱ-free graph with n vertices has minimum degree at most (1- 1/r +o(1))n. On the other hand, the Turán graph T_r(n) is ℱ-free with chromatic number r and δ(T_r(n))=(1- 1/r +o(1))n. Therefore, for any c≤ r-1,
δ_χ(ℱ, c)=1-1  r.  So the remaining challenge is to determine δ_χ(ℱ, c) for c≥χ (ℱ)-1.

We can define the chromatic profile for a family k-uniform graphs similarly (one can also modify the minimum degree condition to minimum co-degree condition). Following from the definitions, we can see that for a non-degenerate family ℱ  of k-uniform graphs (π(ℱ)>0), ℱ is degree-stable with respect to the family of all r-colorable k-uniform graphs if and only if δ_χ(ℱ, r)≤π(ℱ).



The first study of chromatic profile is due to  Andrásfai, Erdős and Sós <cit.>, they showed that if G is a K_r+1-free graph on n vertices with  δ(G)>3r-4/3r-1n, then  χ(G)≤ r. Furthermore they gave an example  G with δ(G)=3r-4/3r-1n and χ(G)=r. In other words, they showed that δ_χ(K_r+1, r)=3r-4/3r-1.  Let C_k denote a cycle with k vertices. In the same paper, Andrásfai, Erdős and Sós <cit.> showed that δ_χ({C_3,C_5,⋯, C_2k+1}, 2)=2/2k+3. Häggkvist <cit.> showed that δ_χ(C_2k+1, 2)=2/2k+3 for k={1,2,3,4}. Recently, Yuan-Peng<cit.> obtained the chromatic profile for any family consisting of some odd cycles, they showed that for a family 𝒞 of odd cycles in which C_2p+1 is the shortest odd cycle not in 𝒞, and C_2k+1 is the longest odd cycle in 𝒞, we have  δ_χ(𝒞, 2)=max{1/2(2p+1), 2/2k+3}. More precisely, the authors showed the following result.
<cit.> 
Let  n≥ 1000k^8 be positive integers.  Let 𝒞 be a family of some odd cycles in which C_2p+1 is the shortest odd cycle not in 𝒞 and C_2k+1 is the longest odd cycle in 𝒞.  Let BC_2p+1(n) denote the graph obtained by taking 2p+1 vertex-disjoint copies of K_n/2(2p+1),n/2(2p+1) and selecting a vertex in each of them such that these vertices form a cycle of length 2p+1. Let C_2k+3(n  2k+3) denote the balanced blow up of C_2k+3 with n vertices.  If G is an n-vertex 𝒞-free graph with δ(G)>max{n/2(2p+1), 2/2k+3n}, then G is bipartite. Graphs BC_2p+1(n) and C_2k+3(n  2k+3) indicate that the bound is tight. Furthermore, the only n-vertex 𝒞-free  non-bipartite graph with minimum degree max{n/2(2p+1), 2/2k+3n}=n/2(2p+1) is BC_2p+1(n), and the  only n-vertex 𝒞-free  non-bipartite graph with minimum degree max{n/2(2p+1), 2/2k+3n}=2/2k+3n is C_2k+3(n  2k+3).




When c≥χ (ℱ), we know very few results on δ_χ(ℱ, c). The only known exact results are  δ_χ(K_3, 3)=10/29 by Häggkvist <cit.> and Jin <cit.>, and δ_χ(K_3, c)=1/3 for every c≥4 by Brandt and Thomassé <cit.>,  δ_χ(K_r+1, r+1)=1-19/19r-9 and δ_χ(K_r+1, r+2)=1-2/2r-1 by Nikiforov <cit.>. Thomassen <cit.> showed that δ_χ(C_5, c)≤6/c and gave an upper bound for δ_χ(C_2k+1, c), together with the recent result of Ma <cit.> (it is not the main focus in <cit.>), we have

    Ω((c+1)^-8(k+1))=δ_χ(C_2k+1, c)=O(k/c).

Recently, Böttcher, Frankl, Cecchelli, Parzcyk and Skokan <cit.> showed that δ_χ({C_3,C_5,⋯, C_2k-1},3)≤1/2k+t for k≥ 45t+5490. Van Ngoc and Tuza <cit.> showed that δ_χ({C_3,C_5,⋯, C_2k-1},3)≥3/2k^2+k+1. In <cit.>, they gave a very detailed introduction about the development of this question.


 In this paper we come up with a different method to determine δ_χ(𝒞, r) for all r≥ 3, 2p≥ r+1 and k≥ 3r+4,  where 𝒞 is a family of  some odd cycles, C_2p+1 is the shortest odd cycle  in 𝒞, and C_2k+1 is the longest odd cycle in 𝒞. In particular, we can determine δ_χ(C_2k+1, r) for all r≥ 3 and k≥ 3r+4.
 We also improve the requirement on n in Theorem <ref> when k≥ 4p+1.
Let us state our main results Precisely.

Let G_r+1 denote the graph obtained by taking r+1 vertex-disjoint copies of K_n/2(r+1),n/2(r+1) and selecting a vertex in each of them such that these vertices form a K_r+1. See the figure below.




Recall that Häggkvist <cit.> showed that δ_χ(C_2k+1, 2)=2/2k+3 for k={1,2,3,4}. In the same paper, Häggkvist pointed out that this result can not be extended to k≥ 5 by giving a counterexample which is G_3.

Our main result is the following.

Let r, k and n be integers with r≥ 3,  k≥ 3r+4 and n≥ 108(r+1)^rk. Let G be an n-vertex C_2k+1-free graph. If

    δ(G)≥n/2r+2,

then G is r-partite, or G=G_r+1.


Theorem <ref> implies the following.

 δ_χ(C_2k+1, r)=1/2r+2 for r≥ 3 and k≥ 3r+4.
 

 
Let  r≥ 3 be an integer.   If G≠ G_r+1 is  a non r-partite n-vertex  graph with
δ(G)≥n/2r+2,
then C_2k+1⊂ G for all k∈ [3r+4, 1/108(r+1)^rn].


Let r≥ 3 and 𝒞 be a family consisting of some  odd cycles in which C_2p+1 is the shortest  cycle  in 𝒞 and C_2k+1 is the longest  cycle in 𝒞 satisfying 2p≥ r+1 and k≥ 3r+4. Clearly δ_χ(𝒞, r)≤δ_χ(C_2k+1, r)=1/2r+2. On the other hand, G_r+1 does not contain any odd cycle longer than r+1, and the shortest cycle in 𝒞   has length 2p+1> r+1, so G_r+1 is 𝒞-free. Note that G_r+1 has the minimum degree n/2r+2 and χ(G_r+1)=r+1, thus, δ_χ(𝒞, r)≥1/2r+2. To summarize, we have the following corollary.


Let r≥ 3 and 𝒞 be a family of odd cycles in which C_2p+1 is the shortest  cycle  in 𝒞 and C_2k+1 is the longest  cycle in 𝒞 satisfying 2p≥ r+1 and k≥ 3r+4. Then
 δ_χ(𝒞, r)=1/2r+2.
 

 For r=2 and any family consisting  of  some odd cycles, we obtain an improvement on the condition of n in Theorem <ref> when k is large relative to p. 
 
 Let k≥ 4p+1 and n≥ 108(2p+1)^2pk be positive integers.  Let 𝒞 be a family of odd cycles in which C_2p+1 is the shortest odd cycle not in 𝒞 and C_2k+1 is the longest odd cycle in 𝒞.  Let BC_2p+1(n) denote the graph obtained by taking 2p+1 vertex-disjoint copies of K_n/2(2p+1),n/2(2p+1) and selecting a vertex in each of them such that these vertices form a cycle of length 2p+1.  If G is an n-vertex 𝒞-free graph with δ(G)≥n/2(2p+1), then G is bipartite or G=BC_2p+1(n).
 
 Note that max{n/2(2p+1), 2/2k+3n}=n/2(2p+1) if and only if  k≥ 4p+1, thus
 the condition k≥ 4p+1 in Theorem <ref>  is tight.
  

 
 



We follow standard notations through. For S⊆ V(G), G[S] denotes the subgraph of G induced by S. Let N_S(v) denote the set of all neighbors of v in G[S], and d_S(v)=| N_S(v)|. We use e(S) to denote the number of edges in G[S].
For T⊆ V(G), let G-T denote the subgraph induced by V(G)-T, N_G(T) denotes the union of  the neighborhoods of all vertices of T in G.  For disjoint X,Y⊆ V(G), G[X,Y] denotes the bipartite subgraph of G induced by X and Y, i.e. G[X,Y] consists of all edges incident to one vertex in X and one vertex in Y.  Use e(X,Y) to denote the number of edges in G[X,Y].

Throughout the paper,  P_xy denotes a path with end points x and y. We call a path P an even (odd) path if |V(P)| is even (odd).

Let H be a subgraph of G. We call H a 2k-core of G if for each pair of vertices x, y∈ V(H) there exists an even path P_xy in H of order (the number of vertices) at most 2k. Furthermore, We call H a strong-2k-core of G if for each pair of vertices x, y∈ V(H), there exists an even path P_xy in H of order at most 2k and there exists an odd path P'_xy in H of order at most 2k.

The concept  strong-2k-core introduced in this paper is crucial to the proof of both Theorems <ref> and <ref>. Methods used in <cit.> and other related papers cannot be applied to obtain Theorems <ref> and <ref>.




§ PROOFS OF THEOREMS <REF> AND <REF>

We first  prove some crucial lemmas.


Let r≥ 2, k and n be integers with n≥108(r+1)^rk and k≥ f(r), where f(r)=2r+1 if r=2 and f(r)=3r+4 if r≥ 3. Let G be a C_2k+1-free graph on n vertices with δ(G)≥n/2r+2, then for any even path P_xy of order at most 2k, we have |(N(x)∩ N(y))∖ V(P_xy)|≤ 15r.

Proof of Lemma <ref>. We show that if there exists an even path P_xy of order at most 2k satisfying |(N(x)∩ N(y))∖ V(P_xy)|>15r, then there is a C_2k+1 in G. We prove it by  induction on 2k-|V(P_xy)|. If |V(P_xy)|=2k, then it is clear that there is a C_2k+1 in G if |(N(x)∩ N(y))∖ V(P_xy)|≥1. Suppose that it holds for 2k≥ |V(P_xy)|≥ 2l+2. Next, we will show that it holds for |V(P_xy)|=2l. Assume that there exist an even path P_xy of order 2l such that |(N(x)∩ N(y))∖ V(P_xy)|> 15r. Let U⊂ (N(x)∩ N(y))∖ V(P_xy) with |U|=15r. If there exists u, v∈ U such that |(N(u)∩ N(v))∖ V(P_xy)|> 15r, then there is an even path P_uv=uP_xyv of order 2l+2 such that |(N(u)∩ N(v))∖ V(P_uv)|> 15r. By induction hypothesis there is a C_2k+1 in G. Therefore we may assume that |(N(u)∩ N(v))∖ V(P_xy)|≤ 15r for any u, v∈ U. Combining with δ(G)≥n/2r+2, we have

    | V(G)|   ≥   (n/2r+2-|V(P_xy)|)|U|-|U| 215r 
       ≥   (n/2r+2-2k)15r-(15r)^3/2
    
    
    
       >    n

by  k≥ f(r), n≥ 108(r+1)^rk and direct calculation.
This is a contradiction.
□





Let r≥ 2, k and n be integers with n≥108(r+1)^rk and k≥ f(r), where f(r)=2r+1 if r=2 and f(r)=3r+4 if r≥ 3.
Let G be a C_2k+1-free graph on n vertices with δ(G)≥n/2r+2. If H is a 2k-core of G, then |V(H)|≤ 2r+2.

Proof of Lemma <ref>. Suppose that |V(H)|≥ 2r+3, then take U⊂ V(H) such that |U|=2r+3. Since H is a 2k-core of G, by Lemma <ref>, |(N(x)∩ N(y))∖ V(P_xy)|≤ 15r for x, y∈ U, where P_xy is an even path of order at most 2k. Therefore, for r≥ 3, |N(x)∩ N(y)|≤ 15r+2k-2≤ 7k since k≥ 3r+4. Combining with δ(G)≥n/2r+2, we have

    | V(G)|   ≥   n/2r+2|U|-|U| 27k 
       =   (2r+3)n/2r+2-2r+3 27k=n+n/2r+2-2r+3 27k 
    
    
       >   n


by  n≥ 108(r+1)^rk and direct calculation.
This is a contradiction.

For r=2, we have |N(x)∩ N(y)|≤ 15r+2k-2=2k+28. Combining with δ(G)≥n/2r+2=n/6, we have

    | V(G)|   ≥   n/6|U|-|U| 2(2k+28) 
       =   7n/6-7 2(2k+28)=n+n/6-(42k+588) 
    
    
       >   n


by n≥ 108(r+1)^rk, k≥ 5 and direct calculation.
This is a contradiction. □

The following observation is easy to see, but it is very important to our proof.


Let H be a strong-2k-core of G with |V(H)|=l≤ 2k-2. If there exists an even path P_uv⊂ V(G)∖ V(H) such that xu∈ E(G) and xv∈ E(G) for some x∈ V(H) with |V(P_uv)|≤ 2k-l, then V(H)∪ V(P_uv) is a strong-2k-core of G. If there exists a path P_uv⊂ V(G)∖ V(H) (it is possible that u=v) such that xu∈ E(G) and yv∈ E(G) for some x, y∈ V(H) with |V(P_uv)|≤ 2k-l, then V(H)∪ V(P_uv) is a strong-2k-core of G.



Let r≥ 2, k and n be integers with n≥108(r+1)^rk and k≥ f(r), where f(r)=2r+1 if r=2 and f(r)=3r+4 if r≥ 3.
Let G be a C_2k+1-free graph on n vertices with δ(G)≥n/2r+2. If H is a strong-2k-core of G, then |V(H)|≤ r+1.

Proof of Lemma <ref>. Let H be a maximum strong-2k-core of G, i.e., |V(H)| has the maximum cardinality among all strong-2k-cores of G. Suppose on the contrary that V(H)={x_1, x_2,…, x_l} with l≥ r+2. By Lemma <ref>, we have that r+2≤ l≤ 2r+2.  Let

    N_i=N(x_i)∖ V(H)  for 1≤ i≤ l.
 By the maximality of |V(H)| and Fact <ref>, we have that

N_i is an independent set for 1≤ i≤ l and N_i∩ N_j=∅ for 1≤ i<j≤ l.

Fix y_i∈ N_i for 1≤ i≤ l and let 
    N_i^*=N(y_i)∖ V(H).

Claim <ref> says that N_i is an independent set, so we have that

 N^*_i∩  N_i =∅ for 1≤ i≤ l.
 
By the maximality of |V(H)| and Fact <ref>, we have that

N^*_i∩ N_j=∅ and N^*_i∩ N^*_j=∅ for 1≤ i<j≤ l.

Since δ(G)≥n/2r+2, we have that |N_i|≥n/2r+2-l. Claim <ref> says that N_i∩ N_j=∅ for 1≤ i<j≤ l, this implies that  |N(y_i)∩ H|=1, so |N^*_i|≥n/2r+2-1 for 1≤ i≤ l. Combining with Claims <ref>, <ref>, <ref>, we have

    |V(G)|≥∑_i=1^l(|N_i|+|N^*_i|)≥ (r+2)(n/r+1-(2r+3))>n+n/r+1-(r+2)(2r+3)>n

since  n≥ 108(r+1)^rk and k≥ f(r).
A contradiction. □

Note that an odd cycle with length less than 2k+1 in a graph G  is a strong-2k-core of G. Next we show that there exists an odd cycle with length less than 2k+1 in a graph G satisfying the conditions in Theorem <ref> or Theorem <ref>.

Let r≥ 2, k and  n be positive integers.
If  G is a  C_2k+1-free non-bipartite graph on n vertices with δ(G)≥n/2r+2, then G contains an odd cycle with length no more than 2(2r+1)+1.

Proof of Lemma <ref>.
Let C_2m+1=v_1v_2⋯ v_2m+1v_1 be a shortest odd cycle of G. Let

    G'=G-V(C_2m+1).



For any vertex v∈ V(G'), we have d_C_2m+1(v)≤ 2  m≥ 2.

Proof of Claim <ref>. Let m≥ 2.  Suppose on the contrary that there exists a vertex x∈ V(G'), such that d_C_2m+1(x)≥ 3, let {v_i,v_j,v_q}⊆ N_C_2m+1(x), where 1≤ i<j<q≤ 2m+1. We claim that any two vertices of {v_i,v_j,v_q} are not adjacent. Otherwise, without loss of generality,  assume that v_iv_j∈ E(G), then vv_iv_jv is a copy of C_3, a contradiction to C_2m+1 being a shortest cycle. Moreover, C_2m+1 is divided into three paths by {v_i,v_j,v_q}, since C_2m+1 is an odd cycle of G, there is at least one even path (so the length is odd). Without loss of generality, assume that v_qv_q+1⋯ v_2m+1v_1⋯ v_i is an even path of C_2m+1. We have shown that any two vertices of {v_i,v_j,v_q} are not adjacent, so v_iv_i+1⋯ v_jv_j+1⋯ v_q is an odd path with at least 5 vertices, then we use the odd path v_ivv_q to replace the odd path v_iv_i+1⋯ v_jv_j+1⋯ v_q of C_2m+1 to get a shorter odd cycle v_ivv_qv_q+1⋯ v_2m+1v_1⋯ v_i, a contradiction. This completes the proof of Claim <ref>. □

Since C_2m+1 is a shortest odd cycle of G, it does not contain any chord. By Claim <ref> and δ(G)≥n/2r+2, for m≥ 2,

    (2m+1)· (n/2r+2-2)≤ e(C_2m+1,G')≤ 2· (n-2m-1).

This implies that m< 2r+2. Since m is an integer, m≤ 2r+1. This completes the proof of Lemma <ref>. □

If G is a  C_2k+1-free non-bipartite graph on n vertices with δ(G)≥n/2r+2 and k≥ 2r+1, then by Lemma <ref>, G contains an odd cycle with length no more than 2k-1. Therefore, G contains a strong-2k-core with at least 3 vertices. Combining with Lemma <ref>, we have the following corollary.


 Let r≥ 2, k and  n be positive integers with k≥ 2r+1.
If  G is a  C_2k+1-free non-bipartite graph on n vertices with δ(G)≥n/2r+2, then G contains a strong-2k-core H with 3≤| V(H)|≤ r+1.


Now we are ready to give structural information on graphs satisfying the conditions in Theorem <ref> or Theorem <ref>.


Let r≥ 2, k and n be integers with n≥108(r+1)^rk and k≥ f(r), where f(r)=2r+1 if r=2 and f(r)=3r+4 if r≥ 3.
Let G be a non-bipartite C_2k+1-free graph on n vertices with δ(G)≥n/2r+2. Let H be a maximum strong-2k-core of G with  V(H)={x_1, x_2,…, x_l} and 3≤ l≤ r+1.  For each i,  1≤ i≤ l, let

    N_i=N(x_i)∖ V(H),   N^1_i=N(N_i) and N^2_i=N(N^1_i)∖ V(H).

Then the following holds.

(i) If  l=r+1, then for each 1≤ i≤ l, N^1_i and N^2_i are independent sets, |N^1_i|=n/2r+2, |N^2_i|=n/2r+2 and G[N^1_i, N^2_i] forms a complete bipartite graph.

(ii) If  l≤ r, then x_i is a cut vertex for each 1≤ i≤ l.


Proof of Lemma <ref>.
By the maximality of |V(H)| and Fact <ref>, we have that

    N_i  is an independent set and N_i∩ N_j=∅ for 1≤ i<j≤ l.

Since N_i is an independent set, we have that

    N^1_i∩ N_i=∅  for 1≤ i≤ l.

By the maximality of |V(H)| and Fact <ref>, we have that

    N^1_i∩ N_j=∅,  N^1_i∩ N^1_j=∅,   N_i∩ N^2_j=∅,  and N^1_i∩ N^2_j=∅ for 1≤ i≠ j≤ l.


Since δ(G)≥n/2r+2, we have

    |N^1_i|≥n/2r+2  for 1≤ i≤ l.

By the maximality of |V(H)| and Fact <ref>,  for any vertex y ∈ N^1_i and y≠ x_i, we have that N(y)∩ H=∅. Combining with   δ(G)≥n/2r+2, we have

    |N^2_i|≥n/2r+2  for 1≤ i≤ l.


Case (i). l=r+1.


N^1_i is an independent set for 1≤ i≤ l.

Proof of Claim <ref>. Without loss of generality, assume that N^1_1 is not an independent set, and u_1u_2∈ E(G) for some u_1, u_2∈ N^1_1. Let u_3, u_4∈ N_1 such that u_1u_3, u_2u_4∈ E(G). By Fact <ref>, we have u_3=u_4. So {u_1, u_2, u_3} forms a K_3. By Lemma <ref>, |N(u_i)∩ N(u_i+1)|≤ 15r for i∈ [3]. Hence |N_1^1∪ N_1^2|≥ |N(u_1)∪ N(u_2)∪ N(u_3)| ≥3n/2r+2-45r. Combining with (<ref>), (<ref>), and (<ref>),  we have

    | V(G)|   ≥   ∑_i=2^l(|N_i|+|N^1_i|)+|N_1^1∪ N_1^2|
       ≥   r(n/r+1-r)+3n/2r+2-45r 
       >   n-n/r+1-r^2+3n/2r+2-45r 
    
       >   n

since k≥ f(r) and n≥ 108(r+1)^rk.
A contradiction.
□

By Claim <ref>, we have

    N^1_i∩ N^2_i=∅ for 1≤ i≤ l.

 Combining (<ref>), (<ref>),   (<ref>), and  (<ref>),
we have
 
    n=|V(G)|≥∑_i=1^l(|N^1_i|+|N^2_i|)≥(r+1)2n/2r+2=n.

 Therefore,
|N^1_i|=n/2r+2, |N^2_i|=n/2r+2 and G[N^1_i, N^2_i] forms a complete bipartite graph for 1≤ i≤ l. Since G is C_2k+1-free, N^2_i is an independent set.

Case (ii). l≤ r.

Since l≥ 3, in this case, r≥ 3 and k≥ 3r+4.

We show that x_i is a cut vertex for each 1≤ i≤ l. Otherwise,
without loss of generality, suppose that there exists a path P_uv⊆ V(G)∖ V(H) such that x_1u∈ E(G) and x_2v∈ E(G) for x_1, x_2∈ V(H), and assume that |V(P_uv)| has the minimum cardinality. Let A=H∪ V(P_uv). By the maximality of |V(H)| and Fact <ref>, we have |A|≥ 2k+1.
By the minimality of |V(P_uv)| and |H|≤ r, then d_A(x)≤ r for x∈ A. By the minimality of |V(P_uv)| and the maximality of |V(H)| and Fact <ref>, we have that d_A(x)≤ 3 for x∈ V(G)∖ A. Hence

    |A|· (n/2r+2-r)≤ e(A,V(G)∖ A)≤ 3(n-|A|),

then |A|≤(6r+6)n/n-2r(r+1)+3. Recall that |A|≥ 2k+1, k≥ 3r+4 and
n≥ 108r^r-1k, then we get  n<0, a contradiction. Therefore x_i is a cut vertex for 1≤ i≤ l.
□

Now are are ready to prove Theorems <ref> and <ref>.



Proof of Theorem <ref>. Let k≥ 4p+1 and n≥ 108(2p+1)^2pk be positive integers.
Let 𝒞 be a family of odd cycles in which C_2p+1 is the shortest odd cycle not in 𝒞 and C_2k+1 is the longest odd cycle in 𝒞.  Let BC_2p+1(n) denote the graph obtained by taking 2p+1 vertex-disjoint copies of K_n/2(2p+1),n/2(2l+1) and selecting a vertex in each of them such that these vertices form a cycle of length 2p+1.  Let G be an n-vertex 𝒞-free non-bipartite graph with δ(G)≥n/2(2p+1). We are going to show that G=BC_2p+1(n).

Take r=2p in Lemma <ref>.  Notations used in the proof  follow from Lemma <ref>.  For example, H is a maximum strong-2k-core of G with  V(H)={x_1, x_2,…, x_l} and 3≤ l≤ 2p+1.  We claim that l=2p+1. Otherwise,  l<2p+1, since H is a maximum strong-2k-core of G, there must be an odd cycle in H and the length of this cycle is no more than l<2p+1. Recall that C_2p+1 is the shortest odd cycle not in 𝒞, in other words, 𝒞 contains all odd cycles with length less than 2p+1. Thus, H is not 𝒞-free, a contradiction. So we have l=2p+1.

Applying Lemma <ref> (i), we obtain that for each 1≤ i≤ l, N^1_i and N^2_i are independent sets, |N^1_i|=n/2r+2, |N^2_i|=n/2r+2 and G[N^1_i, N^2_i] forms a complete bipartite graph.  Since H is a strong-2k-core of G with 2p+1 vertices and H does not contain any odd cycle shorter than 2p+1, H must be C_2p+1. Therefore G=BC_2p+1(n). This completes the proof of Theorem <ref>. □

Proof of Theorem <ref>.  Let r≥ 2, k and n be integers with n≥108(r+1)^rk and k≥ f(r), where f(r)=2r+1 if r=2 and f(r)=3r+4 if r≥ 3. Let G be a C_2k+1-free graph on n vertices with δ(G)≥n/2r+2, we show that G is r-partite, or G=G_r+1.

We apply induction on r. When r=2, applying Theorem <ref> with 𝒞=C_2k+1 and 2p=2, we are fine. We will show that the conclusion holds for r≥ 3. We will apply Lemma <ref> and  notations used in the proof  follow from Lemma <ref>. For example, H is a maximum strong-2k-core of G with  V(H)={x_1, x_2,…, x_l} and 3≤ l≤ r+1.

Case (i). l=r+1.

By Lemma <ref>,   for each 1≤ i≤ l, N^1_i and N^2_i are independent sets, |N^1_i|=n/2r+2, |N^2_i|=n/2r+2 and G[N^1_i, N^2_i] forms a complete bipartite graph.   If H=K_r+1, then G=G_r+1. If H≠ K_r+1, then χ(G)≤ r.

Case (ii). l≤ r.

By Lemma <ref>, x_i is a cut vertex for 1≤ i≤ l. Let

    H_i={u∈ V(G)∖ V(H)|  there exists a path P_ux_i∖{x_i}⊆ V(G)∖ V(H)} for 1≤ i≤ l.

Clearly,  V(G) is partitioned into V(G)=(∪_i=1^l H_i)∪ H. Therefore it is sufficient to show that G[H_i] is (r-1)-partite. Note that N_i∪ N_i^1⊂ V(H_i)∪{x_i}, by (<ref>), |H_i|≥2n/2r+2-l≥ 108r^r-1k. Note that l≥ 3, then |H_i|≤ n-4n/2r+2+l=(r-1)n/r+1+l. Note that N(x)⊂ H_i∪{x_i} for any x∈ H_i, hence δ (G[H_i])≥δ(G)-1=n/2r+2-1> |V(H_i)|/2r. By induction hypothesis, G[H_i] is (r-1)-partite.
□



Remarks.  Theorems <ref> and <ref> show that for any family 𝒞 consisting of some odd cycles, δ_χ(𝒞, 2) is determined by the length of the shortest odd cycle not in 𝒞, and the length of  the longest odd cycle in 𝒞.  In other words, when we study the equivalent form of the question of determining the maximum minimum degree a 𝒞-free graph G with χ(G)≥ r+1 can have, there are two possible extremal graphs, one is related to the length of the shortest odd cycle not in 𝒞, another is related to the length of  the longest odd cycle in 𝒞. For the case r=2, we have found both extremal graphs (BC_2p+1(n) (see Fig.1) and C_2k+3(n  2k+3) (see Fig.2) in Theorems <ref> and <ref>.  For r≥ 3 and   a family 𝒞 of odd cycles in which C_2p+1 is the shortest  cycle  in 𝒞 and C_2k+1 is the longest  cycle in 𝒞, is it true that δ_χ(𝒞, r)=max{g(p, r), h(k, r)}, where g(p, r)n is the minimum degree of an extremal graph related to the shortest odd cycle C_2p+1 in 𝒞 and h(k, r)n is the minimum degree of an extremal graph related to the longest odd cycle C_2k+1 in 𝒞. We think that G_r+1 in Theorem <ref> is the extremal graph related to the shortest odd cycle C_2p+1 in 𝒞 if 2p+1>r+1 and the reason why we can determine δ_χ(𝒞, r) for 2p≥ r+1 and k≥ 3r+4 might be because that the extremal graph related to the shortest odd cycle `dominates' even though extremal graphs related to the longest odd cycle are mysterious to us. We think that the remaining challenge for other cases might be to determine  possible extremal graphs related to the longest odd cycle C_2k+1 in 𝒞. For the case r=2, it is natural to take C_2k+3(n  2k+3). It seems to be challenge but very interesting to construct a good candidate when r≥ 3.



5
allen
P. Allen, Dense H-free graphs are almost (χ(H)-1)-partite, Elec. J. Combin. 17 (1): Research Paper 21, 1–11, 2010.
alon
N. Alon, B. Sudakov, H-free graphs of large minimum degree, Elec. J. Combin. 13 (2006), R19.
Andrsfi
B. Andrsfái, P. Erdős, V. T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218.
Bal
P. Balister, B. Bollobás, O. Riordan, R. H. Schelp, Graphs with large maximum degree containing no odd cycles of a given length, J. Combin. Theory Ser. B 87 (2003), 366–373.
Brandt
S. Brandt, R. Faudree,  W. Goddard,
Weakly pancyclic graphs,
J. Graph Theory 27 (1998), 141–176.
BrTh
S. Brandt and S. Thomassé, Dense triangle-free graphs are four-colourable: A solution to the Erdős Simonovits problem, http://perso.ens-lyon.fr/stephan.thomasse.
Bottcher
J. Böttcher, N. Frankl, D. Mergoni Cecchelli, O. Parzcyk, J. Skokan, Graphs with large minimum degree and no small odd cycles are 3-colourable, arXiv: 2302.01875v1.
Erdos59
P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38.
Erds
P. Erdős, On some new inequalities concerning extremal properties of graphs,
in: P. Erdős, G. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 77–81.
Erd1966Sta1
P. Erdős, Some recent results on extremal problems in graph theory (Results), In: Theory of Graphs (International Symposium Rome, 1966), Gordon and Breach, New York, Dunod, Paris, 1966, pp. 117–123.
Er
P. Erdős, R. J. Faudree, A. Gyárfás, R. H. Schelp,
Odd cycles in graphs of given minimum degree, In Graph Theory, Combinatorics, and Applications,Vol. 1
(Kalamazoo, MI, 1988),  Wiley, New York, 1991, pp. 407–418.
ES66
P. Erdős, M. Simonovits,
A limit theorem in graph theory, Stud. Sci. Math. Hungar. 1 (1966) 51–57.
ES46
P. Erdős, A.H. Stone,
On the structure of linear graphs,
Bull. Amer. Math. Soc. 52 (1946) 1087–1091.

Erdos
P. Erdős, M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973), 323–334.
Gallai
P. Erdős, T. Gallai, On maximal paths and circuits of graphs, Acta Math. Hungar, 10 (1959), 337–356.
Hggkvist
R. Häggkvist, Odd cycles of specified length in nonbipartite graphs, Graph
Theory (Cambridge, 1981), North-Holland Math Stud, 62, North-Holland, Amsterdam, New York, 1982, pp. 89–99.

Illingworth
F. Illingworth, Minimum degree stability of H-free graphs, Combinatorica 43 (2023), 129–147.
Jin
G. P. Jin, Triangle-free four-chromatic graphs, Discrete Math. 145 (1995), no. 1-3, 151–170.
KNS G. Katona, T. Nemetz and M. Simonovits, On a problem of Turán in the theory of graphs, Mat. Lapok, 15(1964), 228-238.

Kom
J. Komlós, M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory, In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Society Mathematical Studies, pages 295–352. János Bolyai Mathematical Society, Budapest, 1996.
Let
S. Letzter, R. Snyder, The homomorphism threshold of {C_3, C_5}-free graphs, J. Graph Theory 90 (2019), 83–106.
LMRX. Liu, D. Mubayi and C. Reiher, A unified approch to hypergraph stability, J. Combin. Theory Ser. B, 158(2022), 36-62.
Ma
J. Ma, Cycles with consecutive odd lengths, European J. Combin. 52 (2016), 74–78.
Nikiforov1
V. Nikiforov, Chromatic number and mimimum degree of K_r-free graphs, arXiv:1001.2070.
Nikiforov
V. Nikiforov, R. H. Schelp, Paths and cycles in graph of large minimal
degree, J. Graph Theory 47 (2004), 39–52.
Sankar
M. Sankar, Homotopy and the Homomorphism Threshold of Odd Cycles, arXiv: 2206.07525v1.
Simonovits
M. Simonovits, Extremal graph problems with symmetrical extremal graphs, Additional chromatic conditions, Discrete Math. 7 (1974), 349–376.
Sim1966
M. Simonovits,
A method for solving extremal problems in graph theory,
stability problems, in: Theory of Graphs,
Proc. Colloq., Tihany, 1966, Academic Press, New York, (1968), pp. 279–319.
Van
N. Van Ngoc and Z. Tuza, 4-chromatic graphs with large odd girth, Discrete Math. 138 (1995), no. 1-3, 387-392, 14th British Combinatorial Conference (Keele, 1993).
Thomassen
C. Thomassen, On the chromatic number of pentagon-free graphs of large minimum degree, Combinatorica 27 (2007), no. 2, 241–243.
Tur
P. Turán, Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436–452.
Ver
J. Verstraëte, On arithmetic progressions of cycle lengths in graphs, Combinatorics, Probability and Computting 9 (2000), 369–373.
YuanPeng
X. Yuan and Y. Peng, Minimum degree stability of C_2k+1-free graphs, J Graph Theory, (2024), 307–321.
YuanPeng2
X. Yuan and Y. Peng, Degree stability of graphs forbidding odd cycles, (2023), arXiv:2305.02762v1.

