Polynomial minimum degree stability for $3$-chromatic graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.07358
curl -X POST /api/v1/records/arxiv/2606.07358/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.07358/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'