Induced trees in triangle-free graphs (Article No. R41)

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.

Keywords

• Induced
• trees
• triangle-free
• graphs
• Article