\(H\)-free graphs of large minimum degree

Noga Alon ; Benny Sudakov

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

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.

Détail

DOI : 10.37236/1045

Classification : 05C35, 05C15
Mots-clés : chromatic number