Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 257-264 |
| Number of pages | 8 |
| Journal | Discrete Applied Mathematics |
| Volume | 294 |
| DOIs | |
| State | Published - May 15 2021 |
Keywords
- On-line list coloring
- Planar graph
- d-defective painting game
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics