2015/07/23 by Thomas A. Mahoney, Thomas Mahoney, Mahoney, Thomas +4
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #math.CO #msc:05C15 #msc:05C57
paper · pdf · doi:10.48550/arxiv.1507.06513
18 pages. Revised introduction, restructured several proofs
arxiv created 2017/07/05 · arxiv updated 2017/07/07
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 uncolored 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 and Lister want to minimize and maximize the total score, respectively. The best score that each player can guarantee is the sum-color cost of G, written \mathrings(G). The game is an online variant of online sum list coloring. We proe (|V(G)|)/(2α(G)) + (1)/(2) ≤ \frac\mathrings(G)|V(G)| ≤ max\ (|V(H)|)/(α(H)) : H ⊂ G\, where α(G) is the independence number, and we study when equality holds in the bounds. We compute \mathrings(G) for graphs with α(G) = 2. Among n-vertex graphs, we prove that \mathrings is minimized by the star and maximized by the path. We also obtain good bounds on \mathrings(Kr,s).