Some results concerning the complexity of restricted colorings of graphs (Q1186161)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some results concerning the complexity of restricted colorings of graphs |
scientific article |
Statements
Some results concerning the complexity of restricted colorings of graphs (English)
0 references
28 June 1992
0 references
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.
0 references
chromatic index
0 references
chromatic number
0 references
restricted colouring
0 references
complexity
0 references
decision problem
0 references
NP-complete
0 references