Pure pairs. IV. Trees in bipartite graphs

Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1016/j.jctb.2023.02.005

Pure pairs. IV. Trees in bipartite graphs

Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

In this paper we investigate the bipartite analogue of the strong Erdős-Hajnal property. We prove that for every forest H and every τ with 0<τ≤1, there exists ε>0, such that if G has a bipartition (A,B) and does not contain H as an induced subgraph, and has at most (1−τ)|A|⋅|B| edges, then there is a stable set X of G with |X∩A|≥ε|A| and |X∩B|≥ε|B|. No graphs H except forests have this property.

Original language	English (US)
Pages (from-to)	120-146
Number of pages	27
Journal	Journal of Combinatorial Theory. Series B
Volume	161
DOIs	https://doi.org/10.1016/j.jctb.2023.02.005
State	Published - Jul 2023

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Bipartite graph
Induced subgraph
Pure pair
Tree

Access to Document

10.1016/j.jctb.2023.02.005

Cite this

@article{38fcd3fc072f4af5a3f56e2bd2940503,

title = "Pure pairs. IV. Trees in bipartite graphs",

abstract = "In this paper we investigate the bipartite analogue of the strong Erd{\H o}s-Hajnal property. We prove that for every forest H and every τ with 0<τ≤1, there exists ε>0, such that if G has a bipartition (A,B) and does not contain H as an induced subgraph, and has at most (1−τ)|A|⋅|B| edges, then there is a stable set X of G with |X∩A|≥ε|A| and |X∩B|≥ε|B|. No graphs H except forests have this property.",

keywords = "Bipartite graph, Induced subgraph, Pure pair, Tree",

author = "Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier Inc.",

year = "2023",

month = jul,

doi = "10.1016/j.jctb.2023.02.005",

language = "English (US)",

volume = "161",

pages = "120--146",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Pure pairs. IV. Trees in bipartite graphs

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2023/7

Y1 - 2023/7

N2 - In this paper we investigate the bipartite analogue of the strong Erdős-Hajnal property. We prove that for every forest H and every τ with 0<τ≤1, there exists ε>0, such that if G has a bipartition (A,B) and does not contain H as an induced subgraph, and has at most (1−τ)|A|⋅|B| edges, then there is a stable set X of G with |X∩A|≥ε|A| and |X∩B|≥ε|B|. No graphs H except forests have this property.

AB - In this paper we investigate the bipartite analogue of the strong Erdős-Hajnal property. We prove that for every forest H and every τ with 0<τ≤1, there exists ε>0, such that if G has a bipartition (A,B) and does not contain H as an induced subgraph, and has at most (1−τ)|A|⋅|B| edges, then there is a stable set X of G with |X∩A|≥ε|A| and |X∩B|≥ε|B|. No graphs H except forests have this property.

KW - Bipartite graph

KW - Induced subgraph

KW - Pure pair

KW - Tree

UR - http://www.scopus.com/inward/record.url?scp=85149385475&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85149385475&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2023.02.005

DO - 10.1016/j.jctb.2023.02.005

M3 - Article

AN - SCOPUS:85149385475

SN - 0095-8956

VL - 161

SP - 120

EP - 146

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Pure pairs. IV. Trees in bipartite graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this