Journal title
European Journal of Combinatorics
DOI
10.1016/j.ejc.2018.07.004
Issue
2018
Volume
74
Last updated
2024-04-14T07:42:50.007+01:00
Page
27-38
Abstract
The classical stability theorem of Erd˝os and Simonovits states that, for any fixed graph with chromatic number k + 1 ≥ 3, the following holds: every n-vertex graph that is H-free and has within o(n 2 ) of the maximal possible number of edges can be made into the k-partite Tur´an graph by adding and deleting o(n 2 ) edges. In this paper, we prove sharper quantitative results for graphs H with a critical edge, both for the Erd˝os-Simonovits Theorem (distance to the Tur´an graph) and for the closely related question of how close an H-free graph is to being k-partite. In many cases, these results are optimal to within a constant factor.
Symplectic ID
870398
Submitted to ORA
On
Favourite
Off
Publication type
Journal Article
Publication date
02 Aug 2018