Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648885 | Discrete Mathematics | 2010 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Gary MacGillivray, Jacobus Swarts,