Loading...
research article
On some coloring problems in grids
Demange, Marc
•
de Werra, Dominique
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.
Type
research article
Web of Science ID
WOS:000315754000002
Authors
Demange, Marc
•
de Werra, Dominique
Publication date
2013
Published in
Volume
472
Issue
11
Start page
9
End page
27
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
January 20, 2014
Use this identifier to reference this record