{
  "id": "1806.07040",
  "version": "v1",
  "published": "2018-06-19T05:07:04.000Z",
  "updated": "2018-06-19T05:07:04.000Z",
  "title": "Defective and Clustered Colouring of Sparse Graphs",
  "authors": [
    "Kevin Hendrey",
    "David R. Wood"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "An (improper) graph colouring has \"defect\" $d$ if each monochromatic subgraph has maximum degree at most $d$, and has \"clustering\" $c$ if each monochromatic component has at most $c$ vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than $\\frac{2d+2}{d+2} k$ is $k$-choosable with defect $d$. This improves upon a similar result by Havet and Sereni [J. Graph Theory, 2006]. For clustered colouring of graphs with maximum average degree $m$, no $(1-\\epsilon)m$ bound on the number of colours was previously known. The above result with $d=1$ solves this problem. It implies that every graph with maximum average degree $m$ is $\\lfloor \\frac{3}{4}m+1\\rfloor$-choosable with clustering 2. We then prove a series of results for clustered colouring that explore the trade-off between the number of colours and the clustering. For example, we prove that every graph with maximum average degree $m$ is $\\lfloor{\\frac{2}{3}m+1}\\rfloor$-choosable with clustering $O(m)$. As an example, this implies that every biplanar graph is 8-choosable with bounded clustering. This is the first non-trivial result for the clustered version of the earth-moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-19T05:07:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum average degree",
      "clustered colouring",
      "sparse graphs",
      "clustering",
      "first non-trivial result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}