\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Noga Alon and Benny Sudakov}
%
%
\medskip
\noindent
%
%
{\bf $H$-Free Graphs of Large Minimum Degree }
%
%
\vskip 5mm
\noindent
%
%
%
%
We prove the following extension of an old result of Andr\'asfai,
Erd\H{o}s and S\'os. 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.
\bye