Article ID: | iaor19921845 |
Country: | Netherlands |
Volume: | 36 |
Issue: | 1 |
Start Page Number: | 35 |
End Page Number: | 46 |
Publication Date: | Mar 1992 |
Journal: | Discrete Applied Mathematics |
Authors: | Kubale Marek |
The paper considers the complexity of restricted colorings of a graph in which each vertex (or edge) receives one color from a list of permissible colors associated with that vertex (edge). Since the problem is strongly NP-complete, it assumes various restrictions imposed on the number and form of permissible colors and the structure of a graph. In this way some evidence is obtained for comparing the complexity of the restricted vertex coloring problem versus that of edge coloring and a number of results is arrived at about special cases that are either positive (polynomial solvability) or negative (NP-completeness proofs).