| Title:
|
Homomorphism duality for rooted oriented paths (English) |
| Author:
|
Smolíková, Petra |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
41 |
| Issue:
|
3 |
| Year:
|
2000 |
| Pages:
|
631-643 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graph homomorphism |
| Keyword:
|
homomorphism duality |
| Keyword:
|
rooted oriented path |
| MSC:
|
05C20 |
| MSC:
|
05C38 |
| MSC:
|
05C85 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 1033.05051 |
| idMR:
|
MR1795092 |
| . |
| Date available:
|
2009-01-08T19:05:52Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119196 |
| . |
| Reference:
|
[1] Gutjahr W., Welzl E., Woeginger G.: Polynomial graph colourings.Discrete Appl. Math. 35 (1992), 29-46. MR 1138082 |
| Reference:
|
[2] Hell P., Nešetřil J.: On the complexity of $H$-colouring.J. Combin. Theory B 48 (1990), 92-110. MR 1047555 |
| Reference:
|
[3] Hell P., Nešetřil J., Zhu X.: Duality and polynomial testing of tree homomorphisms.Trans. Amer. Math. Soc. 348.4 (1996), 1281-1297. MR 1333391 |
| Reference:
|
[4] 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 |
| Reference:
|
[5] Hell P., Zhou H., Zhu X.: Homomorphisms to oriented cycles.Combinatorica 13 (1993), 421-433. Zbl 0794.05037, MR 1262918 |
| Reference:
|
[6] Hell P., Zhu X.: Homomorphisms to oriented paths.Discrete Math. 132 (1994), 107-114. Zbl 0819.05030, MR 1297376 |
| Reference:
|
[7] Hell P., Zhu X.: The existence of homomorphisms to oriented cycles.SIAM J. Discrete Math. 8 (1995), 208-222. Zbl 0831.05059, MR 1329507 |
| Reference:
|
[8] Nešetřil J., Zhu X.: On bounded tree width duality of graphs.J. Graph Theory 23.2 (1996), 151-162. MR 1408343 |
| Reference:
|
[9] Špičková-Smolíková P.: Homomorfismové duality orientovaných grafů (in Czech).Diploma Thesis, Charles University, 1997. |
| . |
