The full text of this article is unavailable through your IP address: 18.226.98.244
Contents Online
Journal of Combinatorics
Volume 12 (2021)
Number 2
The slow-coloring game on sparse graphs: $k$-degenerate, planar, and outerplanar
Pages: 283 – 302
DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n2.a6
Authors
Abstract
The slow-coloring game is played by Lister and Painter on a graph $G$. Initially, all vertices of $G$ are uncolored. In each round, Lister marks a nonempty set $M$ of uncolored vertices, and Painter colors a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. The score of the game is the sum of the sizes of all sets marked by Lister. The goal of Painter is to minimize the score, while Lister tries to maximize it. We provide strategies for Painter on various classes of graphs whose vertices can be partitioned into a bounded number of sets inducing forests, including $k$-degenerate, acyclically $k$-colorable, planar, and outerplanar graphs. For example, we show that on an $n$-vertex graph $G$, Painter can keep the score to at most $\frac{3k+4}{4} n$ when $G$ is $k$-degenerate, $3.9857n$ when $G$ is acyclically $5$-colorable, $3n$ when $G$ is planar with a Hamiltonian dual, $\frac{8n+3m}{5}$ when $G$ is $4$-colorable with $m$ edges (hence $3.4n$ when $G$ is planar), and $\frac{7}{3} n$ when $G$ is outerplanar.
2010 Mathematics Subject Classification
Primary 05C10, 05C15. Secondary 05C05, 05C57, 05C85.
The research of G. Gutowski was supported by National Science Center of Poland, grant UMO-2016/21/B/ST6/02165.
The research of T. Krawczyk, K. Maziarz, and M. Zając was supported by National Science Center of Poland, grant UMO-2015/17/B/ST6/01873.
The research of D. West was supported by National Natural Science Foundation of China grants NSFC 11871439 and 11971439.
The research of X. Zhu was supported by National Natural Science Foundation of China grant NSFC 11971438.
Received 23 October 2018
Accepted 26 June 2020
Published 16 July 2021