TY - JOUR
T1 - Pure Pairs. V. Excluding Some Long Subdivision
AU - Scott, Alex
AU - Seymour, Paul
AU - Spirkl, Sophie
N1 - Publisher Copyright: © 2023, The Author(s), under exclusive licence to János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature.
PY - 2023/6
Y1 - 2023/6
N2 - A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε> 0 , there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with | A| , | B| ≥ εn . He also proved that for all c> 0 there exists ε> 0 such that for every comparability graph G with n> 1 vertices, there is a pure pair A, B with | A| , | B| ≥ εn1-c ; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c> 0 , and all ℓ1, ℓ2≥ 4 / c+ 9 , there exists ε> 0 such that, if G is an (n> 1) -vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2 , then there is a pure pair A, B in G with | A| ≥ εn and | B| ≥ εn1-c . This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph.
AB - A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε> 0 , there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with | A| , | B| ≥ εn . He also proved that for all c> 0 there exists ε> 0 such that for every comparability graph G with n> 1 vertices, there is a pure pair A, B with | A| , | B| ≥ εn1-c ; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c> 0 , and all ℓ1, ℓ2≥ 4 / c+ 9 , there exists ε> 0 such that, if G is an (n> 1) -vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2 , then there is a pure pair A, B in G with | A| ≥ εn and | B| ≥ εn1-c . This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph.
UR - http://www.scopus.com/inward/record.url?scp=85161966646&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85161966646&partnerID=8YFLogxK
U2 - 10.1007/s00493-023-00025-8
DO - 10.1007/s00493-023-00025-8
M3 - Article
SN - 0209-9683
VL - 43
SP - 571
EP - 593
JO - Combinatorica
JF - Combinatorica
IS - 3
ER -