Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs
Abstract
A graph is ‐free if it has no induced subgraph isomorphic to , and |G| denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that: For every graph , there exists such that in every ‐free graph with |G| there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 07, 2020
- Source ID
- 10.1002/jgt.22556
Entities
People
- Alex Scott
- Jacob Fox
- Maria Chudnovsky
- Paul Seymour
- Sophie Spirkl
Organizations
- National Science Foundation
- Office of Naval Research
- Princeton University
- Stanford University
- United States Army Research Laboratory
- University of Oxford