Journal article
Pure pairs. I. Trees and linear anticomplete pairs
- Abstract:
- The Erdős-Hajnal conjecture asserts that for every graph H there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of cardinality at least |G|c. In this paper, we prove a conjecture of Liebenau and Pilipczuk [10], that for every forest H there exists c > 0, such that every graph G with |G| > 1 contains either an induced copy of H, or a vertex of degree at least c|G|, or two disjoint sets of at least c|G| vertices with no edges between them. It follows that for every forest H there exists c > 0 such that, if G contains neither H nor its complement as an induced subgraph, then there is a clique or stable set of cardinality at least |G|c.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 299.2KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.aim.2020.107396
Authors
- Publisher:
- Elsevier
- Journal:
- Advances in Mathematics More from this journal
- Volume:
- 375
- Article number:
- 107396
- Publication date:
- 2020-09-03
- Acceptance date:
- 2020-08-06
- DOI:
- ISSN:
-
0001-8708
- Language:
-
English
- Keywords:
- Pubs id:
-
1124855
- Local pid:
-
pubs:1124855
- Deposit date:
-
2020-08-10
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier Inc.
- Copyright date:
- 2020
- Rights statement:
- © 2020 Elsevier Inc. All rights reserved.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Elsevier at: https://doi.org/10.1016/j.aim.2020.107396
If you are the owner of this record, you can report an update to it here: Report update to this record