Article ID Journal Published Year Pages File Type
8903541 European Journal of Combinatorics 2018 12 Pages PDF
Abstract
The classical stability theorem of Erdős 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(n2) of the maximal possible number of edges can be made into the k-partite Turán graph by adding and deleting o(n2) edges. In this paper, we prove sharper quantitative results for graphs H with a critical edge, both for the Erdős-Simonovits Theorem (distance to the Turán 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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,