Journal article
Pure pairs. IV. Trees in bipartite graphs
- Abstract:
- In this paper we investigate the bipartite analogue of the strong Erdős-Hajnal property. We prove that for every forest H and every τ with 0 < τ ≤ 1, there exists ε > 0, such that if G has a bipartition (A, B) and does not contain H as an induced subgraph, and has at most (1 − τ)|A| · |B| edges, then there is a stable set X of G with |X ∩ A| ≥ ε|A| and |X∩B| ≥ ε|B|. No graphs H except forests have this property
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 339.4KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jctb.2023.02.005
Authors
- Publisher:
- Elsevier
- Journal:
- Journal of Combinatorial Theory, Series B More from this journal
- Volume:
- 161
- Pages:
- 120-146
- Publication date:
- 2023-03-01
- Acceptance date:
- 2023-02-09
- DOI:
- ISSN:
-
0095-8956
- Language:
-
English
- Keywords:
- Pubs id:
-
1329040
- Local pid:
-
pubs:1329040
- Deposit date:
-
2023-02-19
Terms of use
- Copyright holder:
- Elsevier Inc.
- Copyright date:
- 2023
- Rights statement:
- © 2023 Elsevier Inc. All rights reserved.
- Notes:
- This is the accepted manuscript version of the article. The final version is available from Elsevier at: 10.1016/j.jctb.2023.02.005
If you are the owner of this record, you can report an update to it here: Report update to this record