![](https://d3ilqtpdwi981i.cloudfront.net/TiQASSuU0b_2ch93B-VDQ-xStoE=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/70/fc/cf/70fccfc9-518d-4938-8430-d34e68789ad3/thumbnail_882df4b6-2731-4684-8b9a-158442528e53.jpg)
Article
Making Kr+1-Free Graphs r-partite
arxiv
Document Type
Article
Disciplines
Publication Version
Submitted Manuscript
Publication Date
9-30-2019
Abstract
The Erdő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. Fu¨redi gave a short proof that one can choose α = ε. We give a bound for the relationship of α and ε which is asymptotically sharp as ε → 0.
Copyright Owner
The Authors
Copyright Date
2019
Language
en
File Format
application/pdf
Citation Information
József Balogh, Felix Christian Clemen, Mikhail Lavrov, Bernard Lidický, et al.. "Making Kr+1-Free Graphs r-partite" arxiv (2019) Available at: http://works.bepress.com/bernard-lidicky/63/
This pre-print is made available through arixiv: https://arxiv.org/abs/1910.00028.