pith. sign in

arxiv: 1610.08389 · v2 · pith:T55XNG44new · submitted 2016-10-26 · 🧮 math.CO

Stability results for graphs with a critical edge

classification 🧮 math.CO
keywords graphresultscriticaledgeedgesfreegraphsnumber
0
0 comments X
read the original abstract

The classical stability theorem of Erd\H{o}s and Simonovits states that, for any fixed graph with chromatic number $k+1 \ge 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\'{a}n 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\H{o}s-Simonovits Theorem (distance to the Tur\'{a}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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.