TY - JOUR

T1 - Pure Pairs. II. Excluding All Subdivisions of A Graph

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

N1 - Publisher Copyright:
© 2021, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.

PY - 2021/6

Y1 - 2021/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85109637063&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85109637063&partnerID=8YFLogxK

U2 - 10.1007/s00493-020-4024-1

DO - 10.1007/s00493-020-4024-1

M3 - Article

AN - SCOPUS:85109637063

SN - 0209-9683

VL - 41

SP - 379

EP - 405

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -