Pure pairs. I. Trees and linear anticomplete pairs

Author: 

Chudnovsky, M
Scott, A
Seymour, P
Spirkl, S

Publication Date: 

3 September 2020

Journal: 

Advances in Mathematics

Last Updated: 

2020-10-23T18:56:00.13+01:00

DOI: 

10.1016/j.aim.2020.107396

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.

Symplectic id: 

1124855

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article