Abstract: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 $\rho>0$ such that every $H$-free $n$-vertex graph $G$ with $\delta(G) \geq(2 /(2 g+1)+\varepsilon) 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.
From: Yisai Xue [view email]
[v1]
Fri, 5 Jun 2026 15:04:44 UTC (11 KB)
[v2]
Wed, 2 Sep 2026 07:50:30 UTC (10 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。