| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652941 | Electronic Notes in Discrete Mathematics | 2007 | 7 Pages |
Abstract
We prove that every connected triangle-free graph on n vertices contains an induced tree on vertices, where c is a positive constant. The best known upper bound is . This partially answers questions of Erdős, Saks, and Sós and of Pultr.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
