Making Kr+1-Free Graphs r-partite

Abstract

<p>The Erdos-Simonovits stability theorem states that for all epsilon > 0 there exists alpha > 0 such that if G is a Kr+1-free graph on n vertices with e(G) > ex(n, Kr+1)-alpha n2, then one can remove epsilon n2 edges from G to obtain an r-partite graph. Furedi gave a short proof that one can choose alpha = epsilon. We give a bound for the relationship of alpha and epsilon which is asymptotically sharp as epsilon right arrow 0.</p>