Erdős–Hajnal for graphs with no 5-hole

Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1112/plms.12504

Erdős–Hajnal for graphs with no 5-hole

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

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	American English
Pages (from-to)	997-1014
Number of pages	18
Journal	Proceedings of the London Mathematical Society
Volume	126
Issue number	3
DOIs	https://doi.org/10.1112/plms.12504
State	Published - Mar 2023

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1112/plms.12504

Cite this

@article{6483d2e0c28842fca1782e00c4a75388,

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 = "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 = "American English",

volume = "126",

pages = "997--1014",

journal = "Proceedings of the London Mathematical Society",

issn = "0024-6115",

publisher = "Oxford University Press",

number = "3",

}

TY - JOUR

T1 - Erdős–Hajnal for graphs with no 5-hole

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2023/3

Y1 - 2023/3

N2 - 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.).

AB - 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.).

UR - http://www.scopus.com/inward/record.url?scp=85147263800&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85147263800&partnerID=8YFLogxK

U2 - 10.1112/plms.12504

DO - 10.1112/plms.12504

M3 - Article

SN - 0024-6115

VL - 126

SP - 997

EP - 1014

JO - Proceedings of the London Mathematical Society

JF - Proceedings of the London Mathematical Society

IS - 3

ER -

Erdős–Hajnal for graphs with no 5-hole

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this