Further Effects of Two Directed Cycles on the Complexity of $H$-Colouring

Abstract

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.