{
  "id": "0803.1637",
  "version": "v2",
  "published": "2008-03-11T17:05:56.000Z",
  "updated": "2008-10-25T04:39:33.000Z",
  "title": "Large induced trees in K_r-free graphs",
  "authors": [
    "Jacob Fox",
    "Po-Shen Loh",
    "Benny Sudakov"
  ],
  "comment": "10 pages; minor revisions",
  "categories": [
    "math.CO"
  ],
  "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 \\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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-10-25T04:39:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05",
      "05C35",
      "05C55"
    ],
    "keywords": [
      "large induced trees",
      "complete graph",
      "small multiplicative constants",
      "maximum number",
      "connected triangle-free graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0803.1637F"
    }
  }
}