Article ID Journal Published Year Pages File Type
4656736 Journal of Combinatorial Theory, Series B 2015 6 Pages PDF
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].

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,