F\"uredi and Gunderson showed that ex(n, C₂ₖ₊₁) is achieved only on K/2, /2 if n≥ 4k-2. It is natural to study how far a C₂ₖ₊₁-free graph is from being bipartite.Let T^*(r, n) be obtained by adding a suspension Kᵣ with $1$ suspension point to K-r+1/2, -r+1/2. We show that for integers $r, k$ with 3≤ r≤ 2k-4 and n≥ 20(r+2)²k, if G is a C₂ₖ₊₁-free n-vertex graph with e(G)≥ e(T^*(r, n)), then G is obtained by adding suspensions to a bipartite graph one by one and the total number of vertices in all suspensions minus intersection points is no more than $r-1$. In other words, G=Bᵢ₌₁ᵖ Gᵢ, where B is a bipartite graph, G₁ is a suspension to B, Gⱼ is a suspension to Bᵢ₌₁ʲ⁻¹ Gᵢ for 2≤ j≤ p and ∑ᵢ₌₁ᵖ V(Gᵢ)-V(Gᵢ)∩ V(Bᵢ₌₁ʲ⁻¹ Gᵢ) ≤ r-1. Furthermore, ∑ᵢ₌₁ᵖ V(Gᵢ)-V(Gᵢ)∩ V(Bᵢ₌₁ʲ⁻¹ Gᵢ) = r-1 if and only if G=T^*(r, n). Let d₂(G)=min\|T|: T⊆ V(G), G-T \ is bipartite\ and γ₂(G)=min\|E|: E⊆ E(G), G-E \ is bipartite\. Our structural stability result implies that d₂(G)≤ r-1 and γ₂(G)≤ /2 2+/2 2 under the same condition, which is a recent result of Ren-Wang-Wang-Yang [SIAM J. Discrete Math. 38 (2024)]. They proved d₂(G)≤ r-1 and γ₂(G)≤ /2 2+/2 2 separately. We introduce a new concept strong-$2k$-core which is the key that we can give a stronger structural stability result but a simpler proof.
No takes yet. Share an insight, caveat, or question.
Yan et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: