Induced trees in triangle-free graphs

Simple item page
dc.creatorMatousek, Jiri
dc.creatorSamal, Robert
dc.date2007-11-30
dc.date.accessioned2026-07-07T08:46:21Z
dc.date.available2026-07-07T08:46:21Z
dc.descriptionWe 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 Erdos, Saks, and Sos and of Pultr.
dc.identifierhttps://arxiv.org/abs/0711.4829
dc.identifierhttp://arxiv.org/abs/0711.4829
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/143220
dc.subjectCombinatorics
dc.subject05C55, 05C05
dc.titleInduced trees in triangle-free graphs
dc.typetext

Files

Collections

arXiv