Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653295 | European Journal of Combinatorics | 2016 | 16 Pages |
The dd-defective kk-painting game on a graph GG is played by two players: Lister and Painter. Initially, each vertex has kk tokens and is uncoloured. In each round, Lister chooses a set MM of uncoloured vertices and removes one token from each chosen vertex. Painter colours a subset XX of MM which induces a subgraph G[X]G[X] of maximum degree at most dd. Lister wins the game if at the end of some round, a vertex vv has no more tokens left, and is uncoloured. Otherwise, at some round, all vertices are coloured and Painter wins. We say GG is dd-defective kk-paintable if Painter has a winning strategy in this game. This paper proves that for each surface SS, there is a constant ww such that graphs embedded in SS with edge-width at least ww are 22-defective 44-paintable.