Some results concerning the complexity of restricted colorings of graphs

Some results concerning the complexity of restricted colorings of graphs

0.00 Avg rating0 Votes
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:
Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.