The recognition of bound quivers using edge-coloured homomorphisms

A bound quiver is a digraph together with a collection of specified directed walks. Given an undirected graph G, and a collection of walks I, the bound quiver recognition problem asks: Is there an orientation of G such that each walk in I is directed? We present a polynomial time algorithm for this problem, and a structural characterization of which trees can be oriented as bound quivers. These results are developed using homomorphisms of edge-coloured graphs. Our work includes a classification of the computational complexity of edge-coloured homomorphism, problems where the target is of order at most three. (c) 2005 Elsevier B.V All rights reserved.