Large induced trees in Kr-free graphs

For 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 . When r⩾4, we also show that 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.