Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
✍ Scribed by Maria Chudnovsky; Yori Zwols
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 312 KB
- Volume
- 70
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
Erdős and Hajnal [Discrete Math 25 (1989), 37–52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size n^ɛ(H)^ for some ɛ(H)>0. The Conjecture 1. known to be true for graphs H with |V(H)|≤4. One of the two remaining open cases on five vertices is the case where H is a four‐edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four‐edge path or the complement of a five‐edge path as an induced subgraph contains either a clique or a stable set of size at least n^1/6^. © 2011 Wiley Periodicals, Inc. J Graph Theory