Illingworth, Freddie;
(2023)
Minimum Degree Stability of H-Free Graphs.
Combinatorica
, 43
(1)
pp. 129-147.
10.1007/s00493-023-00010-1.
Preview |
Text
min_deg_stab_accepted.pdf - Accepted Version Download (280kB) | Preview |
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)) \binom{n}{2} 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.
| Type: | Article |
|---|---|
| Title: | Minimum Degree Stability of H-Free Graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s00493-023-00010-1 |
| Publisher version: | http://dx.doi.org/10.1007/s00493-023-00010-1 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | Extremal graph theory, Stability, Chromatic profiles, Chromatic thresholds, Colouring |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10197002 |
Archive Staff Only
 |
View Item |
