Menu
Let \(H\) be a digraph whose vertices are called colours. Informally, an \(H\)-colouring of a digraph \(G\) is an assignment of these colours to the vertices of \(G\) so that adjacent vertices receive adjacent colours. In this paper we continue the study of the \(H\)-colouring problem, that is, the decision problem “Does there exist an \(H\)-colouring of a given digraph \(G\)?”. In particular, we prove that the \(H\)-colouring problem is NP-complete if the digraph \(H\) consists of a directed cycle with two chords, or two directed cycles joined by an oriented path, or is obtained from a directed cycle by replacing some arcs by directed two-cycles, so long as \(H\) does not retract to a directed cycle. We also describe a new reduction which yields infinitely many new infinite families of NP-complete \(H\)-colouring problems.