Erdős‐Rogers Functions for Arbitrary Pairs of Graphs

Let be the largest size of an induced ‐free subgraph that every ‐vertex ‐free graph is guaranteed to contain. We prove that for any triangle‐free graph , Along the way we give a slight improvement of a construction of Erdős‐Frankl‐Rödl for the Brown‐Erdős‐Sós ‐problem when is large. In contrast to our result for , for any ‐free graph containing a cycle, we prove there exists such that For every graph , we prove that there exists such that whenever is a non‐empty graph such that is not contained in any blowup of , then . On the other hand, for graph that is not a clique, and every , we exhibit a ‐free graph such that .