## J. Ne\v{s}et\v{r}il, E. Sopena, L. Vignal

*$T$-preserving homomorphisms of oriented graphs *

Comment.Math.Univ.Carolinae 38,1 (1997) 125-136. **Abstract:**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 $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.

**Keywords:** graph, coloring, homomorphism

**AMS Subject Classification:** 05C

PDF