Journal article
Pure pairs. II. Excluding all subdivisions of a graph
- Abstract:
- We prove for every graph H there exists ɛ > 0 such that, for every graph G with |G|≥2, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least ɛ|G| neighbours, or there are two disjoint sets A, B ⊆ V(G) with |A|,|B|≥ɛ|G| such that no edge joins A and B. It follows that for every graph H, there exists c>0 such that for every graph G, if no induced subgraph of G or its complement is a subdivision of H, then G has a clique or stable set of cardinality at least |G|c. This is related to the Erdős-Hajnal conjecture.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 327.7KB, Terms of use)
-
- Publisher copy:
- 10.1007/s00493-020-4024-1
Authors
- Publisher:
- Springer
- Journal:
- Combinatorica More from this journal
- Volume:
- 41
- Pages:
- 379-405
- Publication date:
- 2021-07-07
- Acceptance date:
- 2020-07-11
- DOI:
- EISSN:
-
1439-6912
- ISSN:
-
0209-9683
- Language:
-
English
- Keywords:
- Pubs id:
-
1118454
- Local pid:
-
pubs:1118454
- Deposit date:
-
2020-07-13
Terms of use
- Copyright holder:
- János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg
- Copyright date:
- 2021
- Rights statement:
- Copyright © 2021, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.
- Notes:
-
This is the accepted manuscript version of the article. The final version is available from Springer at https://doi.org/10.1007/s00493-020-4024-1
If you are the owner of this record, you can report an update to it here: Report update to this record