The complexity of locally injective homomorphisms

A homomorphism f:G→Hf:G→H, from a digraph GG to a digraph HH, is locally injective if the restriction of ff to N−(v)N−(v) is an injective mapping, for each v∈V(G)v∈V(G). The problem of deciding whether such an ff exists is known as the injective HH-colouring problem (INJ-HOMH). In this paper, we classify the problem INJ-HOMH as being either a problem in P or a problem that is NP-complete. This is done in the case where HH is a reflexive digraph (i.e. HH has a loop at every vertex) and in the case where HH is an irreflexive tournament. A full classification in the irreflexive case seems hard, and we provide some evidence as to why this may be the case.