Making K 1-free graphs r-partite

József Balogh, Felix Christian Clemen, Mikhail Lavrov, Bernard Lidický, Florian Pfender

Research output: Contribution to journalArticlepeer-review


The ErdA's-Simonovits stability theorem states that for all ϵ > 0 there exists α > 0 such that if G is a Kr+1-free graph on n vertices with e(G) > ex(n, Kr+1)-α n2, then one can remove ϵn2 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.

Original languageEnglish (US)
JournalCombinatorics Probability and Computing
StatePublished - 2021


  • 05C35
  • 2020 MSC Codes:

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this