کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653295 | 1632763 | 2016 | 16 صفحه PDF | دانلود رایگان |
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.
Journal: European Journal of Combinatorics - Volume 54, May 2016, Pages 35–50