Minimum degree stability of \(H\)-free graphs

DOI10.1007/S00493-023-00010-1arXiv2102.11104OpenAlexW3133426009MaRDI QIDQ6057487

Freddie Illingworth

Publication date: 4 October 2023

Published in: Combinatorica (Search for Journal in Brave)

Abstract: Given an $(r+1)$-chromatic graph $H$, the fundamental edge stability result of ErdH{o}s and Simonovits says that all $n$-vertex $H$-free graphs have at most $$ 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'{a}sfai-ErdH{o}s-S'{o}s theorem and work of Alon and Sudakov.

Full work available at URL: https://arxiv.org/abs/2102.11104

zbMATH Keywords

stabilitycolouringextremal graph theorychromatic profileschromatic thresholds

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

Stability number and minimum degree for (\(a, b, k\))-critical graphs

This page was built for publication: Minimum degree stability of \(H\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057487)