Skip to main content

Excluding paths and antipaths

Author(s): Chudnovsky, Maria; Seymour, Paul D.

To refer to this page use:
Abstract: The ErdAs-Hajnal conjecture states that for every graph H, there exists a constant delta(H)> 0, such that if a graph G has no induced subgraph isomorphic to H, then G contains a clique or a stable set of size at least |V (G)| (delta(H)). This conjecture is still open. We consider a variant of the conjecture, where instead of excluding H as an induced subgraph, both H and H (c) are excluded. We prove this modified conjecture for the case when H is the five-edge path. Our second main result is an asymmetric version of this: we prove that for every graph G such that G contains no induced six-edge path, and G (c) contains no induced four-edge path, G contains a polynomial-size clique or stable set.
Publication Date: Aug-2015
Electronic Publication Date: 5-Aug-2014
Citation: Chudnovsky, Maria, Seymour, Paul. (2015). Excluding paths and antipaths. COMBINATORICA, 35 (389 - 412. doi:10.1007/s00493-014-3000-z
DOI: doi:10.1007/s00493-014-3000-z
ISSN: 0209-9683
EISSN: 1439-6912
Pages: 389 - 412
Type of Material: Journal Article
Journal/Proceeding Title: COMBINATORICA
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.