Homomorphism duality for rooted oriented paths
Smolíková, Petra
Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000), p. 631-643 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2000-01-01
Classification:  05C20,  05C38,  05C85,  05C99 
@article{119196,
     author = {Petra Smol\'\i kov\'a},
     title = {Homomorphism duality for rooted oriented paths},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {41},
     year = {2000},
     pages = {631-643},
     zbl = {1033.05051},
     mrnumber = {1795092},
     language = {en},
     url = {http://dml.mathdoc.fr/item/119196}
}

Smolíková, Petra. Homomorphism duality for rooted oriented paths. Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000) pp. 631-643. http://gdmltest.u-ga.fr/item/119196/

Gutjahr W.; Welzl E.; Woeginger G. Polynomial graph colourings, Discrete Appl. Math. 35 (1992), 29-46. (1992) | MR 1138082

Hell P.; Nešetřil J. On the complexity of $H$-colouring, J. Combin. Theory B 48 (1990), 92-110. (1990) | MR 1047555

Hell P.; Nešetřil J.; Zhu X. Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc. 348.4 (1996), 1281-1297. (1996) | MR 1333391

Hell P.; Nešetřil J.; Zhu X. Duality of graph homomorphisms, Combinatorics, Paul Erdös is Eighty, Vol. 2, Bolyai Society Mathematical Studies, Budapest, 1994, pp.271-282. | MR 1395863

Hell P.; Zhou H.; Zhu X. Homomorphisms to oriented cycles, Combinatorica 13 (1993), 421-433. (1993) | MR 1262918 | Zbl 0794.05037

Hell P.; Zhu X. Homomorphisms to oriented paths, Discrete Math. 132 (1994), 107-114. (1994) | MR 1297376 | Zbl 0819.05030

Hell P.; Zhu X. The existence of homomorphisms to oriented cycles, SIAM J. Discrete Math. 8 (1995), 208-222. (1995) | MR 1329507 | Zbl 0831.05059

Nešetřil J.; Zhu X. On bounded tree width duality of graphs, J. Graph Theory 23.2 (1996), 151-162. (1996) | MR 1408343

Špičková-Smolíková P. Homomorfismové duality orientovaných grafů (in Czech), Diploma Thesis, Charles University, 1997.