Pure pairs. II. Excluding all subdivisions of a graph
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 fol...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2021
|