Polynomial minimum degree stability for $3$-chromatic graphs

Abstract

Let $H$ be a fixed 3-chromatic graph, and let $g\ge 2$ be the smallest integer such that there is no homomorphism $H\to C_{2g+1}$. For every $\epsilon >0$, we prove that there exists a constant $\rho >0$ such that every $H$-free $n$-vertex graph $G$ with $\delta (G)\ge (2/(2g+1)+\epsilon )n$ can be made bipartite by deleting $O\left(n^{2-\rho }\right)$ edges. Thus the sharp qualitative minimum-degree stability theorem for 3-chromatic graphs admits a polynomial strengthening. In particular, this gives an affirmative answer to a question of Illingworth [\textit{Minimum degree stability of $H$-free graphs}, Combinatorica, 43(1):129-147, 2023.] on blow-ups of odd cycles.

arXiv comment8 pages