Online sum-paintability: The slow-coloring game |
| |
Authors: | Thomas Mahoney Gregory J. Puleo Douglas B. West |
| |
Affiliation: | 1. Emporia State University, Emporia, KS, United States;2. Auburn University, Auburn, AL, United States;3. Zhejiang Normal University, Jinhua, China;4. University of Illinois, Urbana, IL, United States |
| |
Abstract: | The slow-coloring game is played by Lister and Painter on a graph . On each round, Lister marks a nonempty subset of the uncolored vertices, scoring points. Painter then gives a color to a subset of that is independent in . 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 , written . The game is an online variant of online sum list coloring.We prove , where is the independence number, and we study when equality holds in the bounds. We compute for graphs with . Among -vertex trees, we prove that is minimized by the star and maximized by the path. We also study . |
| |
Keywords: | Slow-coloring game Sum choosability Sum paintability Hall ratio Complete bipartite graph |
本文献已被 ScienceDirect 等数据库收录! |
|