## Abstract

The Erdős–Hajnal conjecture says that for every graph (Formula presented.) there exists (Formula presented.) such that every graph (Formula presented.) not containing (Formula presented.) as an induced subgraph has a clique or stable set of cardinality at least (Formula presented.). We prove that this is true when (Formula presented.) is a cycle of length five. We also prove several further results: for instance, that if (Formula presented.) is a cycle and (Formula presented.) is the complement of a forest, there exists (Formula presented.) such that every graph (Formula presented.) containing neither of (Formula presented.) as an induced subgraph has a clique or stable set of cardinality at least (Formula presented.).

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

Pages (from-to) | 997-1014 |

Number of pages | 18 |

Journal | Proceedings of the London Mathematical Society |

Volume | 126 |

Issue number | 3 |

DOIs | |

State | Published - Mar 2023 |

## All Science Journal Classification (ASJC) codes

- General Mathematics