Some results concerning the complexity of restricted colorings of graphs (Q1186161)

The complexity of colouring the vertices and edges of a simple graph is considered, where every vertex (or edge) has a set of zero or more forbidden colours and adjacent vertices (or edges) receive different colours. The restricted chromatic number \(\chi(G,F)\) (and the chromatic index \(\chi'(G,F)\), resp.) is the least \(k\) for which there is a restricted \(k\)-colouring of \((G,F)\). The decision problem ``Given a graph \(G\), a forbidding function \(F\) and an integer \(k\), is \(\chi(G,F)\leq k?\)'' is NP-complete even when restricted to bipartite graphs and \(k=5\). A similar result is obtained for the decision problem for edge coloured graphs. Some classes of graphs (as trees and paths) for which optimal colourings can be obtained in polynomial time are mentioned.