Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656736 | Journal of Combinatorial Theory, Series B | 2015 | 6 Pages |
Abstract
Let Tn,pTn,p denote the complete p-partite graph of order n having the maximum number of edges. The following sharpening of Turán's theorem is proved. Every Kp+1Kp+1-free graph with n vertices and e(Tn,p)−te(Tn,p)−t edges contains a p -partite subgraph with at least e(Tn,p)−2te(Tn,p)−2t edges.As a corollary of this result we present a concise, contemporary proof (i.e., one applying the Removal Lemma, a corollary of Szemerédi's regularity lemma) for the classical stability result of Simonovits [25].
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zoltán Füredi,