Three topics in online list coloring
James M. Carraher, Sarah Loeb, Thomas A. Mahoney, Gregory J. Puleo, Mu-Tsun Tsai, Douglas B. West · Journal of Combinatorics · 2014
In online list coloring (introduced by Zhu and by Schauz in 2009), on each round the set of vertices having a particular color in their lists is revealed, and the coloring algorithm chooses an independent subset to receive that color.The paint number of a graph G is the least k such that there is an algorithm to produce a successful coloring with no vertex being shown more than k times; it is at least the choice number.We study paintability of joins with complete or empty graphs, obtaining a partial result toward the paint analogue of Ohba's Conjecture.We also determine upper and lower bounds on the paint number of complete bipartite graphs and characterize 3-paint-critical graphs.