A stability result for $C_{2k+1}$-free graphs

Abstract

A graph $G$ is called $C_{2k+1}$-free if it does not contain any cycle of length $2k+1$. In 1981, Haggkvist, Faudree and Schelp showed that every $n$-vertex triangle-free graph with more than $\frac{(n-1{)}^2}{4}+1$ edges is bipartite. In this paper, we extend their result and show that for $1\le t\le 2k-2$ and $n\ge 318t^{2}k$, every $n$-vertex $C_{2k+1}$-free graph with more than $\frac{(n-t-1{)}^2}{4}+\left(\genfrac{}{}{0ex}{}{t+2}{2}\right)$ edges can be made bipartite by either deleting at most $t-1$ vertices or deleting at most $\left(\genfrac{}{}{0ex}{}{\lfloor \frac{t+2}{2}\rfloor }{2}\right)+\left(\genfrac{}{}{0ex}{}{\lceil \frac{t+2}{2}\rceil }{2}\right)-1$ edges. The construction shows that this is best possible.