ON THE COMPLEXITY OF COLORING BY SUPERDIGRAPHS OF BIPARTITE GRAPHS

Let H be a 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 so that if g is adjacent to g' in G then colour(g) is adjacent to colour(g') in H (i.e., a homomorphism G --> H). In this paper we continue the study of the H-colouring problem, that is, the decision problem 'Is there an H-colouring of a given digraph G?' It follows from a result of Hell and Nesetril that this problem is NP-complete whenever H contains a symmetric odd cycle. We consider digraphs for which the symmetric part of H is bipartite, that is, digraphs H which can be constructed from the equivalence digraph of an undirected bipartite graph by adding some arcs. We establish some sufficient conditions for these H-colouring problems to be NP-complete. A complete classification is established for the subclass of 'partitionable digraphs', which we introduce.