{
  "id": "1807.03768",
  "version": "v1",
  "published": "2018-07-10T17:44:46.000Z",
  "updated": "2018-07-10T17:44:46.000Z",
  "title": "Induced subgraphs of graphs with large chromatic number. XIII. New brooms",
  "authors": [
    "Alex Scott",
    "Paul Seymour"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Gy\\'arf\\'as and Sumner independently conjectured that for every tree $T$, the class of graphs not containing $T$ as an induced subgraph is $\\chi$-bounded, that is, the chromatic numbers of graphs in this class are bounded above by a function of their clique numbers. This remains open for general trees $T$, but has been proved for some particular trees. For $k\\ge 1$, let us say a broom of length $k$ is a tree obtained from a $k$-edge path with ends $a,b$ by adding some number of leaves adjacent to $b$, and we call $a$ its handle. A tree obtained from brooms of lengths $k_1,...,k_n$ by identifying their handles is a $(k_1,...,k_n)$-multibroom. Kierstead and Penrice proved that every $(1,...,1)$-multibroom $T$ satisfies the Gy\\'arf\\'as-Sumner conjecture, and Kierstead and Zhu proved the same for $(2,...,2)$-multibrooms. In this paper give a common generalization: we prove that every $(1,...,1,2,...,2)$-multibroom satisfies the Gy\\'arf\\'as-Sumner conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-10T17:44:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "large chromatic number",
      "induced subgraph",
      "gyarfas-sumner conjecture",
      "clique numbers",
      "remains open"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}