Making K 1-free graphs r-partite

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

doi:10.1017/S0963548320000590

Making K ₁-free graphs r-partite

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

Research output: Contribution to journal › Article › peer-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 language	English (US)
Journal	Combinatorics Probability and Computing
DOIs	https://doi.org/10.1017/S0963548320000590
State	Published - 2021
Externally published	Yes

Keywords

05C35
2020 MSC Codes:

ASJC Scopus subject areas

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

Online availability

10.1017/S0963548320000590

Library availability

Discover UIUC Full Text

Cite this

@article{e16b318263b246b5a584c15f5608a020,

title = "Making K 1-free graphs r-partite",

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{\"u}redi gave a short proof that one can choose α = ϵ. We give a bound for the relationship of α and ϵ which is asymptotically sharp as ϵ → 0.",

keywords = "05C35, 2020 MSC Codes:",

author = "J{\'o}zsef Balogh and Clemen, {Felix Christian} and Mikhail Lavrov and Bernard Lidick{\'y} and Florian Pfender",

note = "Publisher Copyright: {\textcopyright} The Author(s), 2020. Published by Cambridge University Press.",

year = "2021",

doi = "10.1017/S0963548320000590",

language = "English (US)",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - Making K 1-free graphs r-partite

AU - Balogh, József

AU - Clemen, Felix Christian

AU - Lavrov, Mikhail

AU - Lidický, Bernard

AU - Pfender, Florian

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - 05C35

KW - 2020 MSC Codes:

UR - http://www.scopus.com/inward/record.url?scp=85095999807&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85095999807&partnerID=8YFLogxK

U2 - 10.1017/S0963548320000590

DO - 10.1017/S0963548320000590

M3 - Article

AN - SCOPUS:85095999807

SN - 0963-5483

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

ER -