2016/12/14 by Gregory J. Puleo, Douglas B. West, Puleo, Gregory J. +1 · 1 citation
Mathematics · #05C15 #05C57 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C57
paper · pdf · doi:10.48550/arxiv.1612.04702
18 pages, 2 figures. This version includes the proof that the sum-color cost agrees with the interactive sum choice number on trees (formerly a standalone paper)
arxiv created 2017/10/02 · arxiv updated 2017/10/04
The slow-coloring game is played by Lister and Painter on a graph G. On each round, Lister marks a nonempty subset M of the remaining vertices, scoring |M| points. Painter then gives a color to a subset of M that is independent in G. The game ends when all vertices are colored. Painter's goal is to minimize the total score; Lister seeks to maximize it. The score that each player can guarantee doing no worse than is the sum-color cost of G, written \mathring\rm s(G). We develop a linear-time algorithm to compute \mathring\rm s(G) when G is a tree, enabling us to characterize the n-vertex trees with the largest and smallest values. Our algorithm also computes on trees the interactive sum choice number, a parameter recently introduced by Bonamy and Meeks.