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.
Publisher Copyright:
© 2018 Elsevier Inc.
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
SN - 0095-8956
VL - 136
SP - 33
EP - 43
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
ER -