Journal of Combinatorics
Volume 5 (2014)
Three topics in online list coloring
Pages: 115 – 130
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.
paintability, choosability, online list coloring, Ohba’s Conjecture, complete bipartite graph