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.
Authors
- Jacques Verstraëte
- Dhruv Mubayi (ORCID: https://orcid.org/0000-0002-4709-8768)
Institutions
- University of California San Diego (US)
- University of Illinois Chicago (US)
Publication Details
- Journal
- Bulletin of the London Mathematical Society
- Published
- 2024-12-20
- DOI
- https://doi.org/10.1112/blms.13214
- Citations
- 3
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 3.97
Funders
- National Science Foundation