Some results concerning the complexity of restricted colorings of graphs

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).