Large induced trees in K_r-free graphs
| dc.creator | Fox, Jacob | |
| dc.creator | Loh, Po-Shen | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2008-03-11 | |
| dc.date | 2008-10-25 | |
| dc.date.accessioned | 2026-07-07T10:12:46Z | |
| dc.date.available | 2026-07-07T10:12:46Z | |
| dc.description | For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. In this paper, we study the problem of bounding t(G) for graphs which do not contain a complete graph K_r on r vertices. This problem was posed twenty years ago by Erdos, Saks, and Sos. Substantially improving earlier results of various researchers, we prove that every connected triangle-free graph on n vertices contains an induced tree of order \sqrt{n}. When r >= 4, we also show that t(G) >= (\log n)/(4 \log r) for every connected K_r-free graph G of order n. Both of these bounds are tight up to small multiplicative constants, and the first one disproves a recent conjecture of Matousek and Samal. | |
| dc.description | 10 pages; minor revisions | |
| dc.identifier | https://arxiv.org/abs/0803.1637 | |
| dc.identifier | http://arxiv.org/abs/0803.1637 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/172294 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C05; 05C35; 05C55 | |
| dc.title | Large induced trees in K_r-free graphs | |
| dc.type | text |