Pure Pairs. V. Excluding Some Long Subdivision

Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)571-593
Number of pages23
JournalCombinatorica
Volume43
Issue number3
DOIs
StatePublished - Jun 2023

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Pure Pairs. V. Excluding Some Long Subdivision'. Together they form a unique fingerprint.

Cite this