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

Grzegorz Gutowski (Jagiellonian University, Kraków, Poland)

Tomasz Krawczyk (Jagiellonian University, Kraków, Poland)

Krzysztof Maziarz (Jagiellonian University, Kraków, Poland)

Douglas B. West (Zhejiang Normal University, Jinhua, China; and University of Illinois, Urbana, Il., U.S.A.)

Michał Zając (Jagiellonian University, Kraków, Poland)

Xuding Zhu (Zhejiang Normal University, Jinhua, China)

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.

Received 23 October 2018

Accepted 26 June 2020

Published 16 July 2021