TY - JOUR

T1 - Pure pairs. I. Trees and linear anticomplete pairs

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Erdos-Hajnal conjecture

KW - Forests

KW - Induced subgraphs

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

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

U2 - 10.1016/j.aim.2020.107396

DO - 10.1016/j.aim.2020.107396

M3 - Article

AN - SCOPUS:85090190898

JO - Advances in Mathematics

JF - Advances in Mathematics

SN - 0001-8708

M1 - 107396

ER -