2016/05/14 by Ming Han, Han, Ming, Xuding Zhu +1
Computer Science · Mathematics · #Advanced Graph Theory Research #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1605.04415
13 pages, 5 figures
arxiv created 2016/05/14 · arxiv updated 2016/05/17
Assume L is a k-list assignment of a graph G. A d-defective m-fold L-colouring ϕ of G assigns to each vertex v a set ϕ(v) of m colours, so that ϕ(v) ⊆ L(v) for each vertex v, and for each colour i, the set \v: i ∈ ϕ(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.