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

Abstract

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
DOIs
StateAccepted/In press - 2020

Keywords

  • 05C35
  • 2020 MSC Codes:

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Making K <sub>1</sub>-free graphs r-partite'. Together they form a unique fingerprint.

Cite this