Geodesic
$T$-preserving homomorphisms of oriented graphs
Commentationes Mathematicae Universitatis Carolinae, Tome 38 (1997) no. 1, pp. 125-136.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

A homomorphism of an oriented graph $G=(V,A)$ to an oriented graph $G'=(V',A')$ is a mapping $\varphi$ from $V$ to $V'$ such that $\varphi(u)\varphi(v)$ is an arc in $G'$ whenever $uv$ is an arc in $G$. A homomorphism of $G$ to $G'$ is said to be $T$-preserving for some oriented graph $T$ if for every connected subgraph $H$ of $G$ isomorphic to a subgraph of $T$, $H$ is isomorphic to its homomorphic image in $G'$. The $T$-preserving oriented chromatic number $\vec{\chi}_T(G)$ of an oriented graph $G$ is the minimum number of vertices in an oriented graph $G'$ such that there exists a $T$-preserving homomorphism of $G$ to $G'$. This paper discusses the existence of $T$-preserving homomorphisms of oriented graphs. We observe that only families of graphs with bounded degree can have bounded \linebreak $T$-preserving oriented chromatic number when $T$ has both in-degree and out-degree at least two. We then provide some sufficient conditions for families of oriented graphs for having bounded $T$-preserving oriented chromatic number when $T$ is a directed path or a directed tree.
Classification : 05C15, 05C20
Keywords: graph; coloring; homomorphism 
@article{CMUC_1997__38_1_a10,
     author = {Ne\v{s}et\v{r}il, J. and Sopena, E. and Vignal, L.},
     title = {$T$-preserving homomorphisms of oriented graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {125--136},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {1997},
     mrnumber = {1455476},
     zbl = {0886.05062},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1997__38_1_a10/}
}
TY  - JOUR
AU  - Nešetřil, J.
AU  - Sopena, E.
AU  - Vignal, L.
TI  - $T$-preserving homomorphisms of oriented graphs
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1997
SP  - 125
EP  - 136
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMUC_1997__38_1_a10/
LA  - en
ID  - CMUC_1997__38_1_a10
ER  - 
%0 Journal Article
%A Nešetřil, J.
%A Sopena, E.
%A Vignal, L.
%T $T$-preserving homomorphisms of oriented graphs
%J Commentationes Mathematicae Universitatis Carolinae
%D 1997
%P 125-136
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMUC_1997__38_1_a10/
%G en
%F CMUC_1997__38_1_a10
Nešetřil, J.; Sopena, E.; Vignal, L. $T$-preserving homomorphisms of oriented graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 38 (1997) no. 1, pp. 125-136. http://geodesic.mathdoc.fr/item/CMUC_1997__38_1_a10/