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 -