Journal article
Induced subgraph density. VII. The five-vertex path
- Abstract:
-
We prove the Erdős-Hajnal conjecture for the five-vertex path $P_5$; that is, there exists $c > 0$ such that every $n$-vertex graph with no induced $P_5$ has a clique or stable set of size at least $n^c$. This completes the verification of the Erdős-Hajnal conjecture for all five-vertex graphs. Our methods combine probabilistic and structural ideas with the iterative sparsification framework introduced in the third and fourth papers in the series.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 495.8KB, Terms of use)
-
- Publisher copy:
- 10.1112/plms.70133
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- https://ror.org/0439y7842
- Grant:
- EP/X013642/1
- Publisher:
- Wiley
- Journal:
- Proceedings of the London Mathematical Society More from this journal
- Volume:
- 132
- Issue:
- 3
- Article number:
- e70133
- Publication date:
- 2026-03-23
- Acceptance date:
- 2026-02-23
- DOI:
- EISSN:
-
1460-244X
- ISSN:
-
0024-6115
- Language:
-
English
- Pubs id:
-
2381248
- Local pid:
-
pubs:2381248
- Deposit date:
-
2026-02-24
- ARK identifier:
Terms of use
- Copyright holder:
- Nguyen et al
- Copyright date:
- 2026
- Rights statement:
- © 2026 The Authors. Proceedings of the London Mathematical Society is copyright © London Mathematical Society. This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record