On the existence and non-existence of improper homomorphisms of oriented and 2-edge-coloured graphs to reflexive targets.

We consider non-trivial homomorphisms to reflexive oriented graphs in which some pair of adjacent vertices have the same image. By way of a notion of convexity for oriented graphs, we study those oriented graphs that do not admit such homomorphisms. We fully classify those oriented graphs with tree-width 2 that do not admit such homomorphisms and show that it is NP-complete to decide if a graph admits an orientation that does not admit such homomorphisms. We prove analogous results for 2-edge-coloured graphs. We apply our results on oriented graphs to provide a new tool in the study of chromatic number of orientations of planar graphs - a long-standing open problem. [ABSTRACT FROM AUTHOR]