Caterpillars in Erdős–Hajnal

Anita Liebenau, Marcin Pilipczuk, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

9 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 languageEnglish (US)
Pages (from-to)33-43
Number of pages11
JournalJournal of Combinatorial Theory. Series B
Volume136
DOIs
StatePublished - May 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Caterpillars
  • Erdos–Hajnal conjecture
  • Induced subgraphs

Fingerprint

Dive into the research topics of 'Caterpillars in Erdős–Hajnal'. Together they form a unique fingerprint.

Cite this