On the Erd\H{o}s-Rogers function

We show that the Erdős-Rogers function $f_{s,s+1}(n)$ satisfies $$f_{s,s+1}(n) = \Theta( \sqrt{n \log n} )$$ for every $s \ge 2$.

More precisely, we construct a $K_{s+1}$-free graph on $n$ vertices in which every set of at least $C(s)\sqrt{n \log n}$ vertices contains a copy of $K_s$ for some constant $C(s)$, which implies the upper bound.

The matching lower bound follows from a theorem of Joret, Micek, Reed and Smid on the clique chromatic number of a graph.