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.

Price: $4.99

Loading Updating cart...