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 -