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
    0 references

    Identifiers