The recognition of bound quivers using edge-coloured homomorphisms Original Research Article

A bound quiver is a digraph together with a collection of specified directed walks. Given an undirected graph image, and a collection of walks image, the bound quiver recognition problem asks: Is there an orientation of image such that each walk in image 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.