Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite
The electronic journal of combinatorics, Tome 17 (2010)
By using the Szemerédi Regularity Lemma, Alon and Sudakov recently extended the classical Andrásfai-Erdős-Sós theorem to cover general graphs. We prove, without using the Regularity Lemma, that the following stronger statement is true. Given any $(r+1)$-partite graph $H$ whose smallest part has $t$ vertices, there exists a constant $C$ such that for any given $\varepsilon>0$ and sufficiently large $n$ the following is true. Whenever $G$ is an $n$-vertex graph with minimum degree $$\delta(G)\geq\left(1-{3\over 3r-1}+\varepsilon\right)n,$$ either $G$ contains $H$, or we can delete $f(n,H)\leq Cn^{2-{1\over t}}$ edges from $G$ to obtain an $r$-partite graph. Further, we are able to determine the correct order of magnitude of $f(n,H)$ in terms of the Zarankiewicz extremal function.
@article{10_37236_293,
author = {Peter Allen},
title = {Dense {\(H\)-free} graphs are almost \((\chi {(H)-1)\)-partite}},
journal = {The electronic journal of combinatorics},
year = {2010},
volume = {17},
doi = {10.37236/293},
zbl = {1215.05090},
url = {http://geodesic.mathdoc.fr/articles/10.37236/293/}
}
Peter Allen. Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/293
Cité par Sources :