\(H\)-free graphs of large minimum degree
The electronic journal of combinatorics, Tome 13 (2006)
We prove the following extension of an old result of Andrásfai, Erdős and Sós. For every fixed graph $H$ with chromatic number $r+1 \geq 3$, and for every fixed $\epsilon>0$, there are $n_0=n_0(H,\epsilon)$ and $\rho=\rho(H) >0$, such that the following holds. Let $G$ be an $H$-free graph on $n>n_0$ vertices with minimum degree at least $\left(1-{1\over r-1/3}+\epsilon\right)n$. Then one can delete at most $n^{2-\rho}$ edges to make $G$ $r$-colorable.
@article{10_37236_1045,
author = {Noga Alon and Benny Sudakov},
title = {\(H\)-free graphs of large minimum degree},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1045},
zbl = {1085.05036},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1045/}
}
Noga Alon; Benny Sudakov. \(H\)-free graphs of large minimum degree. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1045
Cité par Sources :