Journal article icon

Journal article

Pure pairs VI. Excluding an ordered tree

Abstract:

A pure pair in a graph $G$ is a pair $(Z_1,Z_2)$ of disjoint sets of vertices such that either every vertex in $Z_1$ is adjacent to every vertex in $Z_2$, or there are no edges between $Z_1$ and $Z_2$. With Maria Chudnovsky, we recently proved that, for every forest $F$, every graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair $(Z_1,Z_2)$ with $|Z_1|,|Z_2|$ linear in $|G|$. Here we investigate what we can say about pure pair...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1137/20M1368331

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0003-4489-5988
Publisher:
Society for Industrial and Applied Mathematics Publisher's website
Journal:
SIAM Journal on Discrete Mathematics Journal website
Volume:
36
Issue:
1
Pages:
170-187
Publication date:
2022-01-06
Acceptance date:
2021-07-06
DOI:
EISSN:
1095-7146
ISSN:
0895-4801
Language:
English
Keywords:
Pubs id:
1136530
Local pid:
pubs:1136530
Deposit date:
2021-07-06

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP