zbMATH — the first resource for mathematics

On some coloring problems in grids. (English) Zbl 1257.68071
Summary: 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 \geq 4\) colors. We also show that precoloring extension with 3 colors is NP-complete in subgrids.

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI