2014/09/30 by Tyomkyn, Mykhaylo, Uzzell, Andrew J. · 2 citations
#05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1409.8665
We study the behaviour of Kr+1-free graphs G of almost extremal size, that is, typically, e(G)=ex(n,Kr+1)-O(n). We show that such graphs must have a large amount of 'symmetry', in particular that all but very few vertices of G must have twins. As a corollary, we obtain a new, short proof of a theorem of Simonovits on the structure of extremal graphs with ω(G)≤ r and χ(G)≥ k for fixed k ≥ r ≥ 2.