View article

The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping such that is an edge of H whenever is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.