DOI: 10.5176/2251-1911_CMCGS57
Authors: Marc Demange and Dominique De Werra
Abstract: A bipartite graph G = (V1; V2;E) is said (p; q)- choosable with k colors if, by assigning a list L f1; : : : ; kg of size p to each vertex of V1 and a list L f1; : : : ; kg of size q to each vertex of V2, the related k-list coloring instance is always satisfiable (i.e. there is a k-list-coloring respecting the lists). We characterize the cases (p; q) for which grid graphs are (p; q)- choosable and, if not, we give the complexity of the related k-list colorability problem. Results show that only one case is difficult, namely (p; q) = (2; 3) and k 4. As a corollary we get that list-coloring is NP-hard on grids.
Keywords: List-coloring; (p; q)-choosability; NP-complete problems; Grid graphs.
Updating...