Homomorphism duality for rooted oriented paths

Petra Smolíková

Commentationes Mathematicae Universitatis Carolinae (2000)

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

Abstract

top
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 → 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.

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.