Name
Abstract | ||
|---|---|---|
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 n. When r=4, we also show that t(G)=logn4logr 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.jctb.2008.10.001 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
r-free graph,induced subgraph,n vertex,trees,complete graph k,induced subgraphs trees triangle-free graphs ramsey theory,connected triangle-free graph,connected k,triangle-free graphs,order n,ramsey theory,induced tree,graph g,r vertex,large induced tree,induced subgraphs,complete graph | Discrete mathematics,Combinatorics,Graph toughness,Bound graph,k-vertex-connected graph,Graph power,Induced path,Induced subgraph,Distance-hereditary graph,Factor-critical graph,Mathematics | Journal |
Volume | Issue | ISSN |
99 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
5 | 0.63 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacob Fox | 1 | 276 | 25.20 |
| Po-Shen Loh | 2 | 133 | 18.68 |
| Benny Sudakov | 3 | 1391 | 159.71 |