Induced trees in triangle-free graphs (Q5901518)

Summary: We prove that every connected triangle-free graph on \(n\) vertices contains an induced tree on \(\exp(c\sqrt{\log n}\,)\) vertices, where \(c\) is a positive constant. The best known upper bound is \((2+o(1))\sqrt n\). This partially answers questions of \textit{P. Erdős}, \textit{M. Saks}, and \textit{V.T. Sós} [J. Comb. Theory, Ser. B 41, 61--79 (1986; Zbl 0603.05023)] and of \textit{A. Pultr} [private communication with the authors; see also \textit{R.N. Ball} and \textit{A. Pultr}, Cah. Topol. Géom. Différ. Catég. 45, No.\,1, 2--22 (2004; Zbl 1062.06020)].