Let and be fixed digraphs, and let be a fixed homomorphism of to . The \emph{Homomorphism Factoring Problem with respect} to is described as follows:
INSTANCE: A digraph and a homomorphism of to .
QUESTION: Does there exist a homomorphism of to such that ? That is, can the given homomorphism be factored into the composition of and some homomorphism of to ?We investigate the complexity of this problem and show that it differs from that of the -colouring problem, i.e., the decision problem “is there a homomorphism of a given digraph to the fixed digraph ?”, and of restricted versions of this problem. We identify directed graphs for which any homomorphism factoring problem involving is solvable in polynomial time. By contrast, we prove that for any fixed undirected graph which is not a path on at most four vertices, there exists a fixed undirected graph , which can be chosen to be either a tree or a cycle, and a fixed homomorphism of to such that is NP-complete, and if is such a path then is polynomial.