Minimum degree stability of $H$-free graphs

Abstract

Given an $(r+1)$-chromatic graph $H$, the fundamental edge stability result of Erdős and Simonovits says that all $n$-vertex $H$-free graphs have at most $(1-1/r+o(1))\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, and any $H$-free graph with that many edges can be made $r$-partite by deleting $o(n^2)$ edges. Here we consider a natural variant of this -- the minimum degree stability of $H$-free graphs. In particular, what is the least $c$ such that any $n$-vertex $H$-free graph with minimum degree greater than $cn$ can be made $r$-partite by deleting $o(n^2)$ edges? We determine this least value for all 3-chromatic $H$ and for very many non-3-colourable $H$ (all those in which one is commonly interested) as well as bounding it for the remainder. This extends the Andrásfai-Erdős-Sós theorem and work of Alon and Sudakov.

16 pages, 2 figures. Final version, concluding remarks and open question added

References in corpus (1)

• The chromatic profile of locally colourable graphs

Cited by in corpus (3)

• Ramsey goodness of books revisited
• The chromatic profile of locally colourable graphs
• The chromatic profile of locally bipartite graphs