Induced trees in triangle-free graphs

الأصل · EN

We prove that every connected triangle-free graph on n vertices contains an induced tree on (c√ n) vertices, where c is a positive constant. The best known upper bound is (2+o(1))√ n. This partially answers questions of Erdos, Saks, and Sos and of Pultr.