Contents Online

# Journal of Combinatorics

## Volume 5 (2014)

### Number 1

### Three topics in online list coloring

Pages: 115 – 130

DOI: http://dx.doi.org/10.4310/JOC.2014.v5.n1.a5

#### Authors

#### Abstract

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.

#### Keywords

paintability, choosability, online list coloring, Ohba’s Conjecture, complete bipartite graph