Charles Explorer logo
🇬🇧

Induced trees in triangle-free graphs

Publication at Faculty of Mathematics and Physics |
2007

Abstract

(This paper is an extended abstract) We prove that every connected triangle-free graph on n vertices contains an induced tree on at least exp(const.sqrt(log n)) vertices. This partially answers questions of Pultr and of Erdos, Saks, and Sos.