THE EFFECT OF 2 CYCLES ON THE COMPLEXITY OF COLOURINGS BY DIRECTED-GRAPHS

Let H be a fixed directed graph. An H-colouring of a directed graph D is a mapping f: V(D)→V(H) such that f(x)f(y) is an edge of H whenever xy is an edge of D. We study the following H-colouring problem:. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In an earlier paper [2] it is shown that among semicomplete digraphs H, it is the existence of two directed cycles in H which makes the H-colouring problem (NP-) hard. In this paper we provide further classes of digraphs in which two directed cycles in H make the H-colouring problem NP-hard. These include both classes of dense and of sparse digraphs. There still appears to be no natural conjecture as to what digraphs H give NP-hard H-colouring problems; however, in view of our results, we are led to make such a conjecture for digraphs without sources and sinks. © 1990.