Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite
The electronic journal of combinatorics, Tome 17 (2010)
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl arXiv EuDML
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.
Peter Allen. Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/293
@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/}
}
Cité par Sources :