Homomorphism duality for rooted oriented paths

Smolíková, Petra

Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000) no. 3, pp. 631-643

Résumé

Let $(H,r)$ be a fixed rooted digraph. The $(H,r)$-coloring problem is the problem of deciding for which rooted digraphs $(G,s)$ there is a homomorphism $f:G\to H$ which maps the vertex $s$ to the vertex $r$. Let $(H,r)$ be a rooted oriented path. In this case we characterize the nonexistence of such a homomorphism by the existence of a rooted oriented cycle $(C,q)$, which is homomorphic to $(G,s)$ but not homomorphic to $(H,r)$. Such a property of the digraph $(H,r)$ is called {\it rooted cycle duality } or $*$-{\it cycle duality}. This extends the analogical result for unrooted oriented paths given in [6]. We also introduce the notion of {\it comprimed tree duality}. We show that comprimed tree duality of a rooted digraph $(H,r)$ implies a polynomial algorithm for the $(H,r)$-coloring problem.

Détail

Classification : 05C20, 05C38, 05C85, 05C99
Keywords: graph homomorphism; homomorphism duality; rooted oriented path