Strong spectral stabilities for $C_{2k+1}$-free graphs

Abstract

A stability result due to Ren, Wang, Wang and Yang [SIAM J. Discrete Math. 38 (2024)] shows that if $3\le r\le 2k$ and $n\ge 318(r-2{)}^{2}k$, and $G$ is a $C_{2k+1}$-free graph on $n$ vertices with $e(G)\ge \lfloor (n-r+1{)}^2/4\rfloor +(\genfrac{}{}{0ex}{}{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_{2k+1}$-free graph with chromatic number $\ddot{I}‡(G)\ge r$ for every $r\le 2k$. The second part of this paper concerns the spectral extremal problem for $C_{2k+1}$-free graphs. We denote by $\hat{I}»(G)$ the spectral radius of the adjacency matrix of a graph $G$. Let $T_{n-r+1,2}\circ K_r$ be the graph obtained by identifying a vertex of the complete graph $K_r$ and a vertex of the smaller partite set of the bipartite Turán graph $T_{n-r+1,2}$. Using the spectral techniques, we prove that if $3\le r\le 2k$ and $n\ge 712k$, and $G$ is an $n$-vertex $C_{2k+1}$-free graph with chromatic number $\ddot{I}‡(G)\ge r$, then $\hat{I}»(G)\le \hat{I}»(T_{n-r+1,2}\circ K_r)$, where the equality holds if and only if $G=T_{n-r+1,2}\circ K_r$. 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.

25 pages, any suggestions are welcome