Pure pairs. I. Trees and linear anticomplete pairs

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticle

Abstract

The Erdős-Hajnal conjecture asserts that for every graph H there is a constant c>0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of cardinality at least |G|c. In this paper, we prove a conjecture of Liebenau and Pilipczuk [10], that for every forest H there exists c>0, such that every graph G with |G|>1 contains either an induced copy of H, or a vertex of degree at least c|G|, or two disjoint sets of at least c|G| vertices with no edges between them. It follows that for every forest H there exists c>0 such that, if G contains neither H nor its complement as an induced subgraph, then there is a clique or stable set of cardinality at least |G|c.

Original languageEnglish (US)
Article number107396
JournalAdvances in Mathematics
DOIs
StateAccepted/In press - 2020

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Erdos-Hajnal conjecture
  • Forests
  • Induced subgraphs

Fingerprint Dive into the research topics of 'Pure pairs. I. Trees and linear anticomplete pairs'. Together they form a unique fingerprint.

Cite this