Large induced trees in K_r-free graphs

Details Large induced trees in K_r-free graphs Large induced trees in K_r-free graphs

2008-03-11

arxiv.org/abs/0803.1637v2

Mathematics

Combinatorics

10 pages; minor revisions

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Large induced trees in K_r-free graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large induced trees in K_r-free graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large induced trees in K_r-free graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-286563