Pure pairs. I. Trees and linear anticomplete pairs
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 [11], 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|Gj|, 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.
Collections
Cite this version of the work
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl
(2020).
Pure pairs. I. Trees and linear anticomplete pairs. UWSpace.
http://hdl.handle.net/10012/18524
Other formats
The following license files are associated with this item: