ON THE COMPLEXITY OF COLORING BY VERTEX-TRANSITIVE AND ARC-TRANSITIVE DIGRAPHS

Let H be a fixed directed graph whose vertices are called colours. An H-colouring of a digraph G is an assignment of these colours to the vertices of G such that if x is adjacent to y in G, then colour (x) is adjacent to colour (y) in H (i.e., a homomorphism (G -->H). In this paper the complexity of the H-colouring problem, when the directed graph H is vertex-transitive or arc-transitive, is investigated. In both instances a complete classification is obtained.