TY - JOUR
T1 - Every planar graph is 1-defective (9,2)-paintable
AU - Han, Ming
AU - Kierstead, H. A.
AU - Zhu, Xuding
N1 - Funding Information:
This research is supported by CNSF Grants 11971438 , U20A2068 and 111 project of Ministry of Education of China .
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021/5/15
Y1 - 2021/5/15
N2 - Assume G is a graph, and k,d,m are natural numbers. The d-defective (k,m)-painting game on G is played by two players: Lister and Painter. Initially, each vertex has k tokens and is uncolored. In each round, Lister chooses a set M of vertices and removes one token from each chosen vertex. Painter colors a subset X of M which induces a subgraph G[X] of maximum degree at most d. A vertex v is fully colored if v has received m colors. Lister wins if at the end of some round, there is a vertex with no more tokens left and is not fully colored. Otherwise, at some round, all vertices are fully colored and Painter wins. We say G is d-defective (k,m)-paintable if Painter has a winning strategy in this game. We prove that every planar graph is 1-defective (9,2)-paintable. In addition, our winning strategy also implies that every planar graph is 1-defective [Formula presented]-paintable for any positive m.
AB - Assume G is a graph, and k,d,m are natural numbers. The d-defective (k,m)-painting game on G is played by two players: Lister and Painter. Initially, each vertex has k tokens and is uncolored. In each round, Lister chooses a set M of vertices and removes one token from each chosen vertex. Painter colors a subset X of M which induces a subgraph G[X] of maximum degree at most d. A vertex v is fully colored if v has received m colors. Lister wins if at the end of some round, there is a vertex with no more tokens left and is not fully colored. Otherwise, at some round, all vertices are fully colored and Painter wins. We say G is d-defective (k,m)-paintable if Painter has a winning strategy in this game. We prove that every planar graph is 1-defective (9,2)-paintable. In addition, our winning strategy also implies that every planar graph is 1-defective [Formula presented]-paintable for any positive m.
KW - On-line list coloring
KW - Planar graph
KW - d-defective painting game
UR - http://www.scopus.com/inward/record.url?scp=85101405973&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85101405973&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2021.02.008
DO - 10.1016/j.dam.2021.02.008
M3 - Article
AN - SCOPUS:85101405973
SN - 0166-218X
VL - 294
SP - 257
EP - 264
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -