## 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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 389-412 |

Number of pages | 24 |

Journal | Combinatorica |

Volume | 35 |

Issue number | 4 |

DOIs | |

State | Published - Aug 22 2015 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Keywords

- 05C38
- 05C75