HOMOMORPHISMS OF GRAPHS AND OF THEIR ORIENTATIONS

Consider a set of graphs and all the homomorphisms among them. Change each graph into a digraph by assigning directions to its edges. Some of the homomorphisms preserve the directions and so remain as homomorphisms of the set of digraphs; others do not. We study the relationship between the original set of graph-homomorphisms and the resulting set of digraph-homomorphisms and prove that they are in a certain sense independent. This independence result no longer holds if we start with a proper class of graphs, or if we require that only one direction be given to each edge (unless each homomorphism is invertible, in which case we again prove independence). We also specialize the results to the set consisting of one graph and prove the independence of monoids (groups) of a graph and the corresponding digraph. © 1978 Springer-Verlag.