The complexity of locally injective homomorphisms

A homomorphism f : G → H , from a digraph G to a digraph H , is locally injective if the restriction of f to N − ( v ) is an injective mapping, for each v ∈ V ( G ) . The problem of deciding whether such an f exists is known as the injective H -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 H is a reflexive digraph (i.e.  H has a loop at every vertex) and in the case where H 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.