zbMATH — the first resource for mathematics

Homomorphism duality for rooted oriented paths. (English) Zbl 1033.05051
A rooted digraph \((G,s)\) is a digraph \(G\) with a fixed vertex \(s\). A homomorphism of rooted digraphs is a digraph homomorphism that maps a root to a root. Such a homomorphism \((G,s)\to (H,t)\) is also called \((H,t)\)-coloring of \((G,s)\). Existence of colorings of \((G,s)\) by a rooted oriented path \((H,t)\) is shown to be equivalent to nonexistence of a rooted oriented cycle \((C,g)\) such that \((C,g)\) is \((G,s)\)-colorable but not \((H,t)\)-colorable. Algorithmic issues are addressed, too. These results extend the case of nonrooted digraphs examined by P. Hell, H. Zhou and X. Zhu [Combinatorica 13, 421–433 (1993; Zbl 0794.05037)].
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: EuDML