{
  "id": "2104.07927",
  "version": "v1",
  "published": "2021-04-16T07:07:24.000Z",
  "updated": "2021-04-16T07:07:24.000Z",
  "title": "Induced subgraphs of graphs with large chromatic number. XIV. Excluding a biclique and an induced tree",
  "authors": [
    "Alex Scott",
    "Paul Seymour",
    "Sophie Spirkl"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let H be a tree. It was proved by Rodl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph $K_{t,t}$ as a subgraph, have bounded chromatic number. Kierstead and Penrice strengthened this, showing that such graphs have bounded degeneracy. Here we give a further strengthening, proving that for every tree H, the degeneracy is at most polynomial in t. This answers a question of Bonamy, Pilipczuk, Rzazewski, Thomasse and Walczak.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-16T07:07:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "large chromatic number",
      "induced subgraph",
      "induced tree",
      "complete bipartite graph",
      "bounded chromatic number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}