A $d$-defective $k$-painting game on a graph $G$ is played by two players: Lister and Painter. Initially, each vertex is uncolored and has $k$ tokens. In each round, Lister marks a chosen set $M$ of uncolored vertices and removes one token from each marked vertex. In response, Painter colors vertices in a subset $X$ of $M$ which induce a subgraph $G[X]$ of maximum degree at most $d$. Lister wins the game if at the end of some round there is an uncolored vertex that has no more tokens left. Otherwise, all vertices eventually get colored and Painter wins the game. We say that $G$ is $d$-defective $k$-paintable if Painter has a winning strategy in this game. In this paper we show that every planar graph is 3-defective 3-paintable and give a construction of a planar graph that is not 2-defective 3-paintable.
@article{10_37236_7084,
author = {Grzegorz Gutowski and Ming Han and Tomasz Krawczyk and Xuding Zhu},
title = {Defective 3-paintability of planar graphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/7084},
zbl = {1391.05109},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7084/}
}
TY - JOUR
AU - Grzegorz Gutowski
AU - Ming Han
AU - Tomasz Krawczyk
AU - Xuding Zhu
TI - Defective 3-paintability of planar graphs
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/7084/
DO - 10.37236/7084
ID - 10_37236_7084
ER -
%0 Journal Article
%A Grzegorz Gutowski
%A Ming Han
%A Tomasz Krawczyk
%A Xuding Zhu
%T Defective 3-paintability of planar graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7084/
%R 10.37236/7084
%F 10_37236_7084
Grzegorz Gutowski; Ming Han; Tomasz Krawczyk; Xuding Zhu. Defective 3-paintability of planar graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7084
