{
  "id": "1605.04415",
  "version": "v1",
  "published": "2016-05-14T13:20:38.000Z",
  "updated": "2016-05-14T13:20:38.000Z",
  "title": "Every planar graph is $1$-defective $(9,2)$-paintable",
  "authors": [
    "Ming Han",
    "Xuding Zhu"
  ],
  "comment": "13 pages, 5 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Assume $L$ is a $k$-list assignment of a graph $G$. A $d$-defective $m$-fold $L$-colouring $\\phi$ of $G$ assigns to each vertex $v$ a set $\\phi(v)$ of $m$ colours, so that $\\phi(v) \\subseteq L(v)$ for each vertex $v$, and for each colour $i$, the set $\\{v: i \\in \\phi(v)\\}$ induces a subgraph of maximum degree at most $d$. In this paper, we consider on-line list $d$-defective $m$-fold colouring of graphs, where the list assignment $L$ is given on-line, and the colouring is constructed on-line. To be precise, the $d$-defective $(k,m)$-painting game on a graph $G$ is played by two players: Lister and Painter. Initially, each vertex has $k$ tokens and is uncoloured. In each round, Lister chooses a set $M$ of vertices and removes one token from each chosen vertex. Painter colours a subset $X$ of $M$ which induces a subgraph $G[X]$ of maximum degree at most $d$. A vertex $v$ is fully coloured if $v$ has received $m$ colours. Lister wins if at the end of some round, there is a vertex with no more tokens left and is not fully coloured. Otherwise, at some round, all vertices are fully coloured and Painter wins. We say $G$ is $d$-defective $(k,m)$-paintable if Painter has a winning strategy in this game. This paper proves that every planar graph is $1$-defective $(9,2)$-paintable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-14T13:20:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "planar graph",
      "list assignment",
      "maximum degree",
      "on-line list",
      "painter wins"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}