Making <i>K</i>_<i>r</i>+1-free graphs <i>r</i>-partite

Abstract

Abstract The Erdős–Simonovits stability theorem states that for all ε &gt; 0 there exists α &gt; 0 such that if G is a K r+ 1 -free graph on n vertices with e ( G ) &gt; ex( n , K r +1 )– α n 2 , then one can remove εn 2 edges from G to obtain an r -partite graph. Füredi gave a short proof that one can choose α = ε . We give a bound for the relationship of α and ε which is asymptotically sharp as ε → 0.

Topics & Concepts