{
  "id": "1905.09495",
  "version": "v1",
  "published": "2019-05-23T06:40:54.000Z",
  "updated": "2019-05-23T06:40:54.000Z",
  "title": "Clustered Coloring of Graphs Excluding a Subgraph and a Minor",
  "authors": [
    "Chun-Hung Liu",
    "David R. Wood"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph coloring has bounded clustering if each monochromatic component has bounded size. Equivalently, it is a partition of the vertices into induced subgraphs with bounded size components. This paper studies clustered colorings of graphs, where the number of colors depends on an excluded minor and/or an excluded subgraph. We prove the following results (for fixed integers $s,t$ and a fixed graph $H$). First we show that graphs with no $K_{s,t}$ subgraph and with no $H$-minor are $(s+2)$-colorable with bounded clustering. The number of colors here is best possible. This result implies that graphs with no $K_{s+1}$-minor are $(s+2)$-colorable with bounded clustering, which is within two colors of the clustered coloring version of Hadwiger's conjecture. For graphs of bounded treewidth (or equivalently, excluding a planar minor) and with no $K_{s,t}$ subgraph, we prove $(s+1)$-choosability with bounded clustering, which is best possible. We then consider excluding an odd minor. We prove that graphs with no $K_{s,t}$ subgraph and with no odd $H$-minor are $(2s+1)$-colorable with bounded clustering, generalizing a result of the first author and Oum who proved the case $s=1$. Moreover, at least $s-1$ color classes are stable sets. Finally, we consider the clustered coloring version of a conjecture of Gerards and Seymour and prove that graphs with no odd $K_{s+1}$-minor are $(8s-4)$-colorable with bounded clustering, which improves on previous such bounds.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-23T06:40:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded clustering",
      "graphs excluding",
      "clustered coloring version",
      "paper studies clustered colorings",
      "color classes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}