Author
Korándi, D
Roberts, A
Scott, A
Journal title
Advances in Combinatorics, 2021:9, 17pp
Last updated
2022-01-10T20:48:04.06+00:00
Abstract
Tur\'an's Theorem says that an extremal $K_{r+1}$-free graph is $r$-partite.
The Stability Theorem of Erd\H{o}s and Simonovits shows that if a
$K_{r+1}$-free graph with $n$ vertices has close to the maximal $t_r(n)$ edges,
then it is close to being $r$-partite. In this paper we determine exactly the
$K_{r+1}$-free graphs with at least $m$ edges that are farthest from being
$r$-partite, for any $m\ge t_r(n) - \delta_r n^2$. This extends work by
Erd\H{o}s, Gy\H{o}ri and Simonovits, and proves a conjecture of Balogh, Clemen,
Lavrov, Lidick\'y and Pfender.
Symplectic ID
1103563
Download URL
http://arxiv.org/abs/2004.10685v2
Favourite
Off
Publication type
Journal Article
Publication date
22 Apr 2020
Please contact us with feedback and comments about this page. Created on 08 May 2020 - 22:30.