Author
Scott, A
Seymour, P
Spirkl, S
Journal title
Combinatorica
DOI
10.1007/s00493-023-00025-8
Issue
3
Volume
43
Last updated
2024-03-28T21:49:01.067+00:00
Page
571-593
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
$\epsilon>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|\ge \epsilon n$. He
also proved that for all $c>0$ there exists $\epsilon>0$ such that for every
comparability graph $G$ with $n>1$ vertices, there is a pure pair $A,B$ with
$|A|,|B|\ge \epsilon n^{1-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 $\ell_1, \ell_2\ge
4c^{-1}+9$, there exists $\epsilon>0$ such that, if $G$ is a graph with $n>1$
vertices and no hole of length exactly $\ell_1$ and no antihole of length
exactly $\ell_2$, then there is a pure pair $A,B$ in $G$ with $|A|\ge \epsilon
n$ and $|B|\ge \epsilon n^{1-c}$. This is further strengthened, replacing
excluding a hole by excluding some long subdivision of a general graph.
Symplectic ID
1176186
Favourite
Off
Publication type
Journal Article
Publication date
16 Jun 2023
Please contact us with feedback and comments about this page. Created on 12 May 2021 - 23:05.