Pure pairs. IV. Trees in bipartite graphs

Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 languageEnglish (US)
Pages (from-to)120-146
Number of pages27
JournalJournal of Combinatorial Theory. Series B
StatePublished - Jul 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Bipartite graph
  • Induced subgraph
  • Pure pair
  • Tree


Dive into the research topics of 'Pure pairs. IV. Trees in bipartite graphs'. Together they form a unique fingerprint.

Cite this