TY - JOUR

T1 - Caterpillars in Erdős–Hajnal

AU - Liebenau, Anita

AU - Pilipczuk, Marcin

AU - Seymour, Paul

AU - Spirkl, Sophie

N1 - Funding Information:
Previously at Monash University. Research supported by a DECRA Fellowship (grant number DE17010078) from the Australian Research Council. The author would like to thank for its hospitality the Institute of Informatics, University of Warsaw, where this work was carried out.The research of Marcin Pilipczuk is a part of projects that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No. 714704. (Figure presented.) (Figure presented.)Supported by ONR grant N00014-14-1-0084 and NSF grant DMS-1265563.
Funding Information:
Supported by ONR grant N00014-14-1-0084 and NSF grant DMS-1265563.

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

AN - SCOPUS:85053840341

VL - 136

SP - 33

EP - 43

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -