Pure Pairs. V. Excluding Some Long Subdivision.
Abstract
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 jAj; jBj "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 jAj; jBj "n1c; 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 jAj "n and jBj "n1c. This is further strengthened,
replacing excluding a hole by excluding some \long" subdivision of a general graph.
Collections
Cite this version of the work
Alex Scott, Paul Seymour, Sophie Spirkl
(2023).
Pure Pairs. V. Excluding Some Long Subdivision.. UWSpace.
http://hdl.handle.net/10012/20132
Other formats