Homomorphisms to oriented paths (Q1336655)

A homomorphism of a digraph \(G= (V, A)\) to a digraph \(H= (V', A')\) is a mapping \(f: V\to V'\) of the vertices of \(G\) to the vertices of \(H\) (not necessarily onto) which preserves arcs, i.e., such that \(xy\in A\) implies \(f(x) f(y)\in A'\). If such a homomorphism exists, \(G\) is said to be homomorphic to \(H\) and the notation \(G\to H\) is used. Otherwise the notation \(G\nrightarrow H\) is used. Given an oriented path \(P\), the authors characterize those digraphs \(G\) which are homomorphic to \(P\). The characterization equates the nonexistence of a homomorphism \(G\to P\) with the existence of a homomorphism \(W\to G\), for some oriented path \(W\) which is not homomorphic to \(P\). This result complements the recent polynomial time algorithm of \textit{W. Gutjahr}, \textit{E. Welzl} and \textit{G. Woeginger} to find such a homomorphism (if one exists) [Polynomial graph-colorings, Discrete Appl. Math. 35, No. 1, 29-45 (1992; Zbl 0761.05040)]. Say that \(H\) has tree-duality if \(G\nrightarrow H\) if and only if there is an oriented tree \(T\) such that \(T\to G\) and \(T\nrightarrow H\). The main result in this paper is that oriented paths have tree-duality. In another recent paper with J. Nešetřil, the authors have proved that whenever \(H\) has tree-duality then there is a polynomial algorithm to test for the existence of homomorphisms to \(H\).