Caterpillars in Erdős–Hajnal

Anita Liebenau; Marcin Pilipczuk; Paul Seymour; Sophie Spirkl

doi:10.1016/j.jctb.2018.09.002

Caterpillars in Erdős–Hajnal

Anita Liebenau, Marcin Pilipczuk, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

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

5 Scopus citations

Abstract

Let T be a tree such that all its vertices of degree more than two lie on one path; that is, T is a caterpillar subdivision. We prove that there exists ϵ>0 such that for every graph G with |V(G)|≥2 not containing T as an induced subgraph, either some vertex has at least ϵ|V(G)| neighbours, or there are two disjoint sets of vertices A,B, both of cardinality at least ϵ|V(G)|, where there is no edge joining A and B. A consequence is: for every caterpillar subdivision T, there exists c>0 such that for every graph G containing neither of T and its complement as an induced subgraph, G has a clique or stable set with at least |V(G)| ^c vertices. This extends a theorem of Bousquet, Lagoutte and Thomassé [1], who proved the same when T is a path, and a recent theorem of Choromanski, Falik, Liebenau, Patel and Pilipczuk [2], who proved it when T is a “hook”.

Original language	American English
Pages (from-to)	33-43
Number of pages	11
Journal	Journal of Combinatorial Theory. Series B
Volume	136
DOIs	https://doi.org/10.1016/j.jctb.2018.09.002
State	Published - May 2019

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Caterpillars
Erdos–Hajnal conjecture
Induced subgraphs

Access to Document

10.1016/j.jctb.2018.09.002

Cite this

@article{b2862ebc481b4c529f337374fb48e9af,

title = "Caterpillars in Erd{\H o}s–Hajnal",

abstract = " Let T be a tree such that all its vertices of degree more than two lie on one path; that is, T is a caterpillar subdivision. We prove that there exists ϵ>0 such that for every graph G with |V(G)|≥2 not containing T as an induced subgraph, either some vertex has at least ϵ|V(G)| neighbours, or there are two disjoint sets of vertices A,B, both of cardinality at least ϵ|V(G)|, where there is no edge joining A and B. A consequence is: for every caterpillar subdivision T, there exists c>0 such that for every graph G containing neither of T and its complement as an induced subgraph, G has a clique or stable set with at least |V(G)| c vertices. This extends a theorem of Bousquet, Lagoutte and Thomass{\'e} [1], who proved the same when T is a path, and a recent theorem of Choromanski, Falik, Liebenau, Patel and Pilipczuk [2], who proved it when T is a “hook”.",

keywords = "Caterpillars, Erdos–Hajnal conjecture, Induced subgraphs",

author = "Anita Liebenau and Marcin Pilipczuk and Paul Seymour and Sophie Spirkl",

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

year = "2019",

month = may,

doi = "10.1016/j.jctb.2018.09.002",

language = "American English",

volume = "136",

pages = "33--43",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Caterpillars in Erdős–Hajnal

AU - Liebenau, Anita

AU - Pilipczuk, Marcin

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2019/5

Y1 - 2019/5

N2 - Let T be a tree such that all its vertices of degree more than two lie on one path; that is, T is a caterpillar subdivision. We prove that there exists ϵ>0 such that for every graph G with |V(G)|≥2 not containing T as an induced subgraph, either some vertex has at least ϵ|V(G)| neighbours, or there are two disjoint sets of vertices A,B, both of cardinality at least ϵ|V(G)|, where there is no edge joining A and B. A consequence is: for every caterpillar subdivision T, there exists c>0 such that for every graph G containing neither of T and its complement as an induced subgraph, G has a clique or stable set with at least |V(G)| c vertices. This extends a theorem of Bousquet, Lagoutte and Thomassé [1], who proved the same when T is a path, and a recent theorem of Choromanski, Falik, Liebenau, Patel and Pilipczuk [2], who proved it when T is a “hook”.

AB - Let T be a tree such that all its vertices of degree more than two lie on one path; that is, T is a caterpillar subdivision. We prove that there exists ϵ>0 such that for every graph G with |V(G)|≥2 not containing T as an induced subgraph, either some vertex has at least ϵ|V(G)| neighbours, or there are two disjoint sets of vertices A,B, both of cardinality at least ϵ|V(G)|, where there is no edge joining A and B. A consequence is: for every caterpillar subdivision T, there exists c>0 such that for every graph G containing neither of T and its complement as an induced subgraph, G has a clique or stable set with at least |V(G)| c vertices. This extends a theorem of Bousquet, Lagoutte and Thomassé [1], who proved the same when T is a path, and a recent theorem of Choromanski, Falik, Liebenau, Patel and Pilipczuk [2], who proved it when T is a “hook”.

KW - Caterpillars

KW - Erdos–Hajnal conjecture

KW - Induced subgraphs

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

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

U2 - 10.1016/j.jctb.2018.09.002

DO - 10.1016/j.jctb.2018.09.002

M3 - Article

SN - 0095-8956

VL - 136

SP - 33

EP - 43

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Caterpillars in Erdős–Hajnal

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this