# Homomorphism duality for rooted oriented paths

Commentationes Mathematicae Universitatis Carolinae (2000)

- Volume: 41, Issue: 3, page 631-643
- ISSN: 0010-2628

## Access Full Article

top## Abstract

top## How to cite

topSmolíková, Petra. "Homomorphism duality for rooted oriented paths." Commentationes Mathematicae Universitatis Carolinae 41.3 (2000): 631-643. <http://eudml.org/doc/248582>.

@article{Smolíková2000,

abstract = {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\rightarrow 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 rooted cycle duality or $*$-cycle duality. This extends the analogical result for unrooted oriented paths given in [6]. We also introduce the notion of 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.},

author = {Smolíková, Petra},

journal = {Commentationes Mathematicae Universitatis Carolinae},

keywords = {graph homomorphism; homomorphism duality; rooted oriented path; rooted digraph; graph homomorphism; coloring by digraphs; rooted oriented path; consistency check},

language = {eng},

number = {3},

pages = {631-643},

publisher = {Charles University in Prague, Faculty of Mathematics and Physics},

title = {Homomorphism duality for rooted oriented paths},

url = {http://eudml.org/doc/248582},

volume = {41},

year = {2000},

}

TY - JOUR

AU - Smolíková, Petra

TI - Homomorphism duality for rooted oriented paths

JO - Commentationes Mathematicae Universitatis Carolinae

PY - 2000

PB - Charles University in Prague, Faculty of Mathematics and Physics

VL - 41

IS - 3

SP - 631

EP - 643

AB - 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\rightarrow 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 rooted cycle duality or $*$-cycle duality. This extends the analogical result for unrooted oriented paths given in [6]. We also introduce the notion of 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.

LA - eng

KW - graph homomorphism; homomorphism duality; rooted oriented path; rooted digraph; graph homomorphism; coloring by digraphs; rooted oriented path; consistency check

UR - http://eudml.org/doc/248582

ER -

## References

top- Gutjahr W., Welzl E., Woeginger G., Polynomial graph colourings, Discrete Appl. Math. 35 (1992), 29-46. (1992) MR1138082
- Hell P., Nešetřil J., On the complexity of $H$-colouring, J. Combin. Theory B 48 (1990), 92-110. (1990) MR1047555
- 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) MR1333391
- 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. MR1395863
- Hell P., Zhou H., Zhu X., Homomorphisms to oriented cycles, Combinatorica 13 (1993), 421-433. (1993) Zbl0794.05037MR1262918
- Hell P., Zhu X., Homomorphisms to oriented paths, Discrete Math. 132 (1994), 107-114. (1994) Zbl0819.05030MR1297376
- Hell P., Zhu X., The existence of homomorphisms to oriented cycles, SIAM J. Discrete Math. 8 (1995), 208-222. (1995) Zbl0831.05059MR1329507
- Nešetřil J., Zhu X., On bounded tree width duality of graphs, J. Graph Theory 23.2 (1996), 151-162. (1996) MR1408343
- Špičková-Smolíková P., Homomorfismové duality orientovaných grafů (in Czech), Diploma Thesis, Charles University, 1997.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.