Erdős–Hajnal for graphs with no 5‐hole
Abstract
The Erdős–Hajnal conjecture says that for every graph there exists such that every graph not containing as an induced subgraph has a clique or stable set of cardinality at least . We prove that this is true when is a cycle of length five. We also prove several further results: for instance, that if is a cycle and is the complement of a forest, there exists such that every graph containing neither of as an induced subgraph has a clique or stable set of cardinality at least .
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 31, 2023
- Source ID
- 10.1112/plms.12504
Entities
People
- Alex Scott
- Maria Chudnovsky
- Paul Seymour
- Sophie Spirkl
Organizations
- Air Force Office of Scientific Research
- Engineering and Physical Sciences Research Council
- National Science Foundation
- Natural Sciences and Engineering Research Council
- Princeton University
- University of Oxford
- University of Waterloo