Strong spectral stabilities for C₂₊+₁-free graphs

A stability result due to Ren, Wang, Wang and Yang SIAM J. Discrete Math. 38 (2024) shows that if 3 r 2k and n 318 (r-2) ²k, and G is a C₂₊+₁-free graph on n vertices with e (G) (n-r+1) ²/4 +r 2, then G can be made bipartite by deleting at most r-2 vertices. Using a different method, we give a linear bound on n in terms of k and show a stronger structural result, which roughly says that G can be obtained from a large bipartite graph by suspending some small graphs that the total number of vertices is at most r-2. This improves a result of Yan and Peng (2024) by weakening the requirement on n and k. As a direct corollary, we obtain a tight upper bound on the size of an n-vertex C₂₊+₁-free graph with chromatic number χ (G) r for every r 2k. The second part of this paper concerns the spectral extremal problem for C₂₊+₁-free graphs. We denote by λ (G) the spectral radius of the adjacency matrix of a graph G. Let T₍-ₑ+₁, ₂ Kᵣ be the graph obtained by identifying a vertex of the complete graph Kᵣ and a vertex of the smaller partite set of the bipartite Turán graph T₍-ₑ+₁, ₂. Using the spectral techniques, we prove that if 3 r 2k and n 712k, and G is an n-vertex C₂₊+₁-free graph with chromatic number χ (G) r, then λ (G) λ (T₍-ₑ+₁, ₂ Kᵣ), where the equality holds if and only if G=T₍-ₑ+₁, ₂ Kᵣ. Our result not only extends a result of Guo, Lin and Zhao Linear Algebra Appl. 627 (2021) as well as a result of Zhang and Zhao Discrete Math. 346 (2023), but also provides the first solution to the spectral extremal problem for F-free graphs with high chromatic number.