Longest odd cycles in non-bipartite $C_{2k+1}$-free graphs

Abstract

In strengthening a result of Andrásfai, Erdős and Sós in 1974, Häggkvist proved that if $G$ is an $n$-vertex $C_{2k+1}$-free graph with minimum degree $\delta (G)>\frac{2n}{2k+3}$ and $n>\left(\genfrac{}{}{0ex}{}{k+2}{2}\right)(2k+3)(3k+2)$, then $G$ contains no odd cycle of length greater than $\frac{k+1}{2}$. This result has many applications.In this paper, we consider a similar problem by replacing minimum degree condition with edge number condition. We prove that for integers $n,k,r$ with $k\ge 2,3\le r\le 2k$ and $n\ge 2\left(r+2\right)\left(r+1\right)\left(r+2k\right)$, if $G$ is an $n$-vertex $C_{2k+1}$-free graph with $e(G)\ge \lfloor \frac{(n-r+1{)}^2}{4}\rfloor +\left(\genfrac{}{}{0ex}{}{r}{2}\right)$, then $G$ contains no odd cycle of length greater than $r$. The construction shows that the result is best possible. This extends a result of Brandt [Discrete Applied Mathematics 79 (1997)], and a result of Bollobás and Thomason [Journal of Combinatorial Theory, Series B. 77 (1999)], and a result of Caccetta and Jia [Graphs Combin. 18 (2002)] and independently proving by Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)]. Recently, Ren, Wang, Yang, and the second author [SIAM J. Discrete Math. 38 (2024)] show that for $3\le r\le 2k$ and $n\ge 318(r-2{)}^{2}k$, every $n$-vertex $C_{2k+1}$-free graph with $e(G)\ge \lfloor \frac{(n-r+1{)}^2}{4}\rfloor +\left(\genfrac{}{}{0ex}{}{r}{2}\right)$ can be made bipartite by deleting at most $r-2$ vertices or deleting at most $\left(\genfrac{}{}{0ex}{}{\lfloor \frac{r}{2}\rfloor }{2}\right)+\left(\genfrac{}{}{0ex}{}{\lceil \frac{r}{2}\rceil }{2}\right)$ edges. As an application, we derive this result and provide a simple proof.