The slow-coloring game on sparse graphs: $k$-degenerate, planar, and outerplanar

Grzegorz Gutowski, Tomasz Krawczyk, Krzysztof Maziarz, Douglas B. West, Michał Zając, Xuding ZhuJournal of Combinatorics 2021 · DOI · arXiv

Abstract

The slow-coloring game is an adversarial graph coloring game played by two players, Lister and Painter. In each round, Lister marks a set of uncolored vertices, and Painter selects an independent subset to color. The objective is to determine the "sum-color cost," which Lister seeks to maximize and Painter seeks to minimize. This paper provides improved upper bounds for this cost across several sparse graph classes, including $k$-degenerate, planar, and outerplanar graphs. By employing two novel strategies—the Decomposition Method and the Potential Method—we demonstrate that Painter can maintain scores significantly lower than those suggested by traditional chromatic number bounds.

Introduction

In traditional graph theory, the chromatic number $\chi(G)$ represents the minimum number of colors needed to color a graph such that no two adjacent vertices share the same color. The slow-coloring game introduces a dynamic, round-based constraint to this concept.

The game proceeds as follows:

  1. Lister marks a non-empty set $M$ of currently uncolored vertices.
  2. Painter chooses a subset $X \subseteq M$ that is an independent set in $G$ and colors it.
  3. The game continues until all vertices are colored.

The score of the game is the sum of the sizes of all sets $M$ marked by Lister. We denote the maximum score Lister can guarantee on a graph $G$ as the sum-color cost, $\mathring{s}(G)$. While a trivial upper bound for any graph is $\chi(G) \cdot n$, this research explores how the structural sparsity of certain graph classes allows Painter to achieve much lower scores.

Methodological Framework

To provide tighter upper bounds, the authors introduce two primary mathematical strategies for Painter.

1. The Decomposition Method

This method relies on the principle of "divide and conquer." If a graph $G$ can be partitioned into subgraphs with known coloring costs (such as forests or independent sets), Painter can combine optimal strategies from these subgraphs. The authors prove a composition theorem: if the vertex set of $G$ can be partitioned into $V_1, \dots, V_k$, then the total cost $\mathring{s}(G)$ is bounded by the sum of the costs of the induced subgraphs plus a factor related to how they interact. This is particularly effective for $k$-degenerate graphs, which can be decomposed into forests.

2. The Potential Method

The Potential Method is a sophisticated accounting technique. Each vertex and edge in the graph is assigned a "potential" value (a positive real number). In each round, Painter’s goal is to select an independent set $X$ from Lister's marked set $M$ such that the reduction in the graph's total potential is at least as large as the size of $M$. If Painter can consistently find such a set, the total score of the game is guaranteed to be no more than the initial total potential of the graph. To facilitate this, the authors utilize "good $k$-colorings" to ensure that a sufficiently large independent set always exists within any $M$.

Key Results

The paper establishes several new upper bounds for the sum-color cost $\mathring{s}(G)$ on an $n$-vertex graph:

  • Planar Graphs: For any planar graph, the cost is at most $3.4n$. This is a notable improvement over the $4n$ bound derived from the Four Color Theorem. For the specific subclass of planar graphs with a Hamiltonian dual, the bound improves further to $3n$.
  • Outerplanar Graphs: These graphs, which can be embedded in the plane such that all vertices lie on the outer boundary, have a cost of at most $\frac{7}{3}n \approx 2.33n$.
  • k-Degenerate Graphs: For graphs where every subgraph has a vertex of degree at most $k$, the cost is at most $\frac{3k+4}{4}n$ (for even $k$). For example, 2-degenerate graphs (such as circle graphs) have a bound of $2.5n$.
  • Acyclically 5-colorable Graphs: The authors provide a bound of $3.9857n$. While all planar graphs are acyclically 5-colorable, the specific planar bound of $3.4n$ remains the stronger result for that specific class.

Discussion and Future Work

These results demonstrate that the sum-color cost of sparse graphs is often much lower than the product of the chromatic number and the number of vertices. However, the authors acknowledge that these bounds may not yet be "sharp." The Decomposition Method, while powerful, does not fully account for edges between different partitions, which a clever Lister might exploit.

Future research directions include:

  1. Lower Bounds: Developing strategies for Lister to determine how close these upper bounds are to the absolute minimum score.
  2. Refined Potential Functions: Adjusting the weights assigned to edges and vertices to further tighten the results for planar and $k$-degenerate graphs.
  3. Expanded Graph Classes: Applying these methods to graphs with bounded treewidth or other structural constraints.

Summary updated

Abstract

The \emph{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}4n$ 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 $\frac73n$ when $G$ is outerplanar.
BibTeX
@article{gutowski2021slow,
  author = {Grzegorz Gutowski and Tomasz Krawczyk and Krzysztof Maziarz and Douglas B. West and Michał Zając and Xuding Zhu},
  title = {{The slow-coloring game on sparse graphs: $k$-degenerate, planar, and outerplanar}},
  journal = {Journal of Combinatorics},
  year = {2021},
  doi = {10.4310/joc.2021.v12.n2.a6},
}
Figure