On the order of the classical Erdős–Rogers functions

Abstract

For an integer , the Erdős–Rogers function is the maximum integer such that every ‐vertex ‐free graph has a ‐free induced subgraph with vertices. It is known that for all , as . In this paper, we show that for all , there exists a constant such that This improves previous bounds of order by Dudek, Retter and Rödl and answers a question of Warnke.