On some coloring problems in grids

We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of the bipartition are all of size p and lists in the second part are of size q. In particular, we characterize the complexity of (p, q)-List coloring in grid graphs, showing that the only NP-complete case is (2, 3)-List coloring with k >= 4 colors. We also show that Precoloring extension with 3 colors is NP-complete in subgrids. (C) 2012 Elsevier B.V. All rights reserved.