2018/10/01 by Anita Liebenau, Liebenau, Anita, Marcin Pilipczuk +5
Arts and Humanities · Computer Science · Earth and Planetary Sciences · Mathematics · #Advanced Graph Theory Research #Ancient and Medieval Archaeology Studies #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Marine and environmental studies #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1810.00811
openalex publication_date 2018/10/01 · openalex created_date 2021/06/22 · openalex updated_date 2026/07/28
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é [JCTB 2015], who proved the same when T is a path, and a recent theorem of Choromanski, Falik, Liebenau, Patel and Pilipczuk [Electron. J. Combin. 2018], who proved it when T is a "hook".