@article{468c9d03ad564a6192e59e10a37e742b,

title = "Erd{\H o}s–Hajnal for graphs with no 5-hole",

abstract = "The Erd{\H o}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.).",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Funding Information: Maria Chudnovsky supported by NSF Grant DMS 1763817. Alex Scott research supported by EPSRC Grant EP/V007327/1. Paul Seymour supported by AFOSR Grants A9550‐19‐1‐0187 and FA9550‐22‐1‐0234, and by NSF Grants DMS‐1800053 and DMS‐2154169. We acknowledge the Sophie Spirkl support of the Natural Sciences and Engineering Research Council of Canada (NSERC; funding reference number RGPIN‐2020‐03912). Cette recherche a {\'e}t{\'e} financ{\'e}e par le Conseil de recherches en sciences naturelles et en g{\'e}nie du Canada (CRSNG), [num{\'e}ro de r{\'e}f{\'e}rence RGPIN‐2020‐03912]. Funding Information: Maria Chudnovsky: research supported by NSF Grant DMS 1763817. Alex Scott: research supported by EPSRC Grant EP/V007327/1. Paul Seymour: research supported by AFOSR Grants A9550-19-1-0187 and FA9550-22-1-0234, and by NSF Grants DMS-1800053 and DMS-2154169. Sophie Spirkl: We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC; funding reference number RGPIN-2020-03912). Cette recherche a {\'e}t{\'e} financ{\'e}e par le Conseil de recherches en sciences naturelles et en g{\'e}nie du Canada (CRSNG), [num{\'e}ro de r{\'e}f{\'e}rence RGPIN-2020-03912]. Publisher Copyright: {\textcopyright} 2023 The Authors. Proceedings of the London Mathematical Society is copyright {\textcopyright} London Mathematical Society.",

year = "2023",

month = mar,

doi = "10.1112/plms.12504",

language = "English (US)",

volume = "126",

pages = "997--1014",

journal = "Proceedings of the London Mathematical Society",

issn = "0024-6115",

publisher = "Oxford University Press",

number = "3",

}