Abstract
For graphs and , let be the minimum possible size of a maximum ‐free induced subgraph in an ‐vertex ‐free graph. This notion generalizes the Ramsey function and the Erdős–Rogers function. Establishing a container lemma for the ‐free subgraphs, we give a general upper bound on , assuming the existence of certain locally dense ‐free graphs. In particular, we prove that for every graph with , where , we have For the cases where is a complete multipartite graph, letting , we prove that We also make an observation which improves the bounds of by a polylogarithmic factor.
Funding Information
  • National Science Foundation (DMS‐1764123, DMS‐1937241, DMS‐2152488)
  • University of Illinois at Urbana-Champaign

This publication has 22 references indexed in Scilit: