Journal article icon

Journal article

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

Abstract:

The Erdős–Hajnal conjecture says that for every graph 𝐻 there exists 𝜏>0 such that every graph𝐺not con-taining𝐻as an induced subgraph has a clique or stable set of cardinality at least |𝐺|𝜏. We prove that this is true when 𝐻 is a cycle of length five. We also prove several further results: for instance, that if 𝐶 is a cycle and 𝐻 is the complement of a forest, there exists 𝜏>0 such that every graph 𝐺 containing neither of 𝐶,𝐻 as an induced subgraph has a clique or stable set of cardinality at least|𝐺|𝜏.

Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1112/plms.12504

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0003-4489-5988
Publisher:
London Mathematical Society
Journal:
Proceedings of the London Mathematical Society More from this journal
Volume:
126
Issue:
3
Pages:
997-1014
Publication date:
2023-01-31
Acceptance date:
2022-10-14
DOI:
EISSN:
1460-244X
ISSN:
0024-6115
Language:
English
Keywords:
Pubs id:
1161639
Local pid:
pubs:1161639
Deposit date:
2022-11-02

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP