{"id":"arxiv/2606.07358","url":"https://arxiv.org/abs/2606.07358","tags":["math.CO"],"score":0,"title":"Polynomial minimum degree stability for $3$-chromatic graphs","domain":"math.CO","source":"arxiv","authors":["Yisai Xue"],"reviews":0,"subject":"math.CO","summary":"Let $H$ be a fixed 3-chromatic graph, and let $g \\geq 2$ be the smallest integer such that there is no homomorphism $H \\rightarrow C_{2 g+1}$. For every $\\varepsilon>0$, we prove that there exists a constant $ρ>0$ such that every $H$-free $n$-vertex graph $G$ with $δ(G) \\geq(2 /(2 g+1)+\\varepsilon) n$ can be made bipartite by deleting $O\\left(n^{2-ρ}\\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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-05","reactions":{}}