Journal of Combinatorics

Volume 5 (2014)

Number 1

Three topics in online list coloring

Pages: 115 – 130

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

Authors

James Carraher (Department of Mathematics, University of Nebraska, Lincoln, Neb., U.S.A.)

Sarah Loeb (Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Thomas Mahoney (Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Gregory J. Puleo (Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Mu-Tsun Tsai (Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Douglas B. West (Department of Mathematics, Zhejiang Normal University, Jinhua, Zhejiang, China; Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

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

Full Text (PDF format)

Published 12 February 2014