# 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)].
##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 05C85 Graph algorithms (graph-theoretic aspects)
Full Text: