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.


Published in:
Theoretical Computer Science, 472, 11, 9-27
Year:
2013
ISSN:
0304-3975
Keywords:
Laboratories:




 Record created 2014-01-20, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)