Excluding paths and antipaths

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

The Erdős-Hajnal conjecture states that for every graph H, there exists a constant δ(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)|δ(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 Hc 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 Gc contains no induced four-edge path, G contains a polynomial-size clique or stable set.

Original languageEnglish (US)
Pages (from-to)389-412
Number of pages24
JournalCombinatorica
Volume35
Issue number4
DOIs
StatePublished - Aug 22 2015

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • 05C38
  • 05C75

Fingerprint

Dive into the research topics of 'Excluding paths and antipaths'. Together they form a unique fingerprint.

Cite this