Parameter Augmentation for Two Formulas
2006
We prove the following extension of an old result of Andrasfai, Erdős and Sos. 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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
23
Citations
NaN
KQI