Large cliques or stable sets in graphs with no four‐edge path and no five‐edge path in the complement |
| |
Authors: | Maria Chudnovsky Yori Zwols |
| |
Institution: | 1. Department of Industrial Engineering and Operations Research, Columbia University, , New York, New York;2. School of Computer Science, Mcgill University, , Montreal, QC, Canada |
| |
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 n1/6. © 2011 Wiley Periodicals, Inc. J Graph Theory |
| |
Keywords: | Erdő s– Hajnal conjecture forbidden induced subgraphs |
|
|