The effect of two cycles on the complexity of colourings by directed graphs (Q911612)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The effect of two cycles on the complexity of colourings by directed graphs
scientific article

    Statements

    The effect of two cycles on the complexity of colourings by directed graphs (English)
    0 references
    1990
    0 references
    Let H be a fixed digraph. An H-colouring of a digraph D is a mapping f: V(D)\(\to V(H)\) such that if xy is an arc in D then f(x)f(y) is an arc in H. The authors discuss various classes of digraphs H in which the existence of two directed cycles makes the H-colouring problem NP-hard.
    0 references
    0 references
    graph colouring
    0 references
    digraphs
    0 references
    directed cycles
    0 references
    H-colouring problem
    0 references
    NP-hard
    0 references
    0 references
    0 references
    0 references
    0 references