Pure pairs. I. Trees and linear anticomplete pairs

Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1016/j.aim.2020.107396

Pure pairs. I. Trees and linear anticomplete pairs

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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 language	American English
Article number	107396
Journal	Advances in Mathematics
Volume	375
DOIs	https://doi.org/10.1016/j.aim.2020.107396
State	Published - Dec 2 2020

ASJC Scopus subject areas

General Mathematics

Keywords

Erdos-Hajnal conjecture
Forests
Induced subgraphs

Access to Document

10.1016/j.aim.2020.107396

Cite this

@article{37c20b37e9394e608fa287888a41d0e0,

title = "Pure pairs. I. Trees and linear anticomplete pairs",

abstract = "The Erd{\H o}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.",

keywords = "Erdos-Hajnal conjecture, Forests, Induced subgraphs",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2020",

month = dec,

day = "2",

doi = "10.1016/j.aim.2020.107396",

language = "American English",

volume = "375",

journal = "Advances in Mathematics",

issn = "0001-8708",

publisher = "Academic Press Inc.",

}

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/12/2

Y1 - 2020/12/2

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

SN - 0001-8708

VL - 375

JO - Advances in Mathematics

JF - Advances in Mathematics

M1 - 107396

ER -

Pure pairs. I. Trees and linear anticomplete pairs

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this