  Extending the concept of Ramsey numbers, Erd{\H o}s and Rogers introduced the
following function. For given integers $2\le s<t$ let $$ f_{s,t}(n)=\min \{\max
\{|W| : W\subseteq V(G) {and} G[W] {contains no} K_s\} \}, $$ where the minimum
is taken over all $K_t$-free graphs $G$ of order $n$. In this paper, we show
that for every $s\ge 3$ there exist constants $c_1=c_1(s)$ and $c_2=c_2(s)$
such that $f_{s,s+1}(n) \le c_1 (\log n)^{c_2} \sqrt{n}$. This result is best
possible up to a polylogarithmic factor. We also show for all $t-2 \geq s \geq
4$, there exists a constant $c_3$ such that $f_{s,t}(n) \le c_3 \sqrt{n}$. In
doing so, we partially answer a question of Erd\H{o}s by showing that
$\lim_{n\to \infty} \frac{f_{s+1,s+2}(n)}{f_{s,s+2}(n)}=\infty$ for any $s\ge
4$.
