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.
@article{118908,
author = {Jaroslav Ne\v set\v ril and Eric Sopena and Laurence Vignal},
title = {$T$-preserving homomorphisms of oriented graphs},
journal = {Commentationes Mathematicae Universitatis Carolinae},
volume = {38},
year = {1997},
pages = {125-136},
zbl = {0886.05062},
mrnumber = {1455476},
language = {en},
url = {http://dml.mathdoc.fr/item/118908}
}
Nešetřil, Jaroslav; Sopena, Eric; Vignal, Laurence. $T$-preserving homomorphisms of oriented graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 38 (1997) pp. 125-136. http://gdmltest.u-ga.fr/item/118908/
An acyclic analogue to Heawood's theorem, Glasgow Math. J. 19 (1978), 163-166. (1978) | MR 0485490 | Zbl 0378.05030
Acyclic colorings of graphs, Random Structures and Algorithms 2 (1991), 277-289. (1991) | MR 1109695
On acyclic colorings of planar graphs, Discrete Math. 25 (1979), 211-236. (1979) | MR 0534939 | Zbl 0406.05031
On the maximum average degree and the oriented chromatic number of a graph, preprint, 1995. | MR 1665387
Some theorems on abstract graphs, Proc. London. Math. Soc. 2 (1952), 69-81. (1952) | MR 0047308 | Zbl 0047.17001
On $A$-mote universal graphs, European J. Combin. 13 (1993), 23-27. (1993) | MR 1197472
On the complexity of $H$-coloring, J. Combin. Theory Series B 48 (1990), 92-110. (1990) | MR 1047555
Duality theorems and polynomial tree-coloring, Trans. Amer. Math. Soc., to appear.
Duality of graph homomorphisms, Combinatorics, Paul Erdös is eighty, Vol. 2, Bolyai Society Mathematical Studies, 1993. | MR 1395863
Graph Coloring Problems, Wiley Interscience, 1995. | MR 1304254 | Zbl 0855.05054
Note to the paper of Grünbaum on acyclic colorings, Discrete Math. 14 (1976), 403-406. (1976) | MR 0404037 | Zbl 0318.05103
Acyclic and oriented chromatic numbers of graphs, preprint 95-087, Univ. Bielefeld, 1995. | MR 1437294 | Zbl 0873.05044
Colorings and interpretations: a connection between graphs and grammar forms, Discrete Applied Math. 3 (1981), 119-135. (1981) | MR 0607911 | Zbl 0466.05034
Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12. (1964) | MR 0161333 | Zbl 0119.38805
Homomorphisms of derivative graphs, Discrete Math. 1 -3 (1971), 257-268. (1971) | MR 0300939
Colorings and girth of oriented planar graphs, Research Report 1084-95, Univ. Bordeaux I, 1995.
On bounded treewidth duality of graph homomorphisms, J. Graph Theory, to appear. | MR 1408343
Good and semi-strong colorings of oriented planar graphs, Inf. Processing Letters 51 (1994), 171-174. (1994) | MR 1294309 | Zbl 0806.05031
The chromatic number of oriented graphs, Research Report 1083-95, Univ. Bordeaux I, 1995. | Zbl 0874.05026
Personal communication, 1995.