## 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 | |

State | Published - 2021 |

## 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_{1}-free graphs r-partite'. Together they form a unique fingerprint.