Induced Trees in Triangle-Free Graphs

  • Jiří Matoušek
  • Robert Šámal

Abstract

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 Erdős, Saks, and Sós and of Pultr.

Published
2008-03-12
Article Number
R41