Large induced trees in Kr-free graphs

AbstractFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. In this paper, we study the problem of bounding t(G) for graphs which do not contain a complete graph Kr on r vertices. This problem was posed twenty years ago by Erdős, Saks, and Sós. Substantially improving earlier results of various researchers, we prove that every connected triangle-free graph on n vertices contains an induced tree of order n. When r⩾4, we also show that t(G)⩾logn4logr for every connected Kr-free graph G of order n. Both of these bounds are tight up to small multiplicative constants, and the first one disproves a recent conjecture of Matoušek and Šámal