The Slow-Coloring Game on Path Power Graphs

Abstract

The Slow-Coloring Game is a game played on a graph G by two players which we will refer to as Lister and Painter. In the ith round, Lister marks a nonempty subset M of V (G) of uncolored vertices as eligible to receive color i, scoring |M| points. Painter then gives color i to a subset of M that is independent in G. The game ends when all of the vertices of G are colored. Note that at each stage the resulting coloring will be a proper coloring of V(G). Lister’s goal is to maximize the total score while Painter seeks to minimize the total score. The sum-color cost of a graph G, denoted s(G), is the best score each player can guarantee in the Slow-Coloring Game on G regardless of the play strategy of the other. Puleo and West gave upper and bounds for the sum-color cost for every tree T on n vertices. They also conjectured that this bound generalizes to k-trees. Mahoney, Puleo, and West provide the value for the sum-color cost of k-stars, we provide the value for the sum-color cost of k-paths.