$T$-preserving homomorphisms of oriented graphs
Jaroslav Nešetřil, Éric Sopena, L. Vignal · Czech digital mathematics library · 1997
. A homomorphism of an oriented graph G = (V; A) to an oriented graph G 0 = (V 0 ; A 0 ) is a mapping ' from V to V 0 such that '(u)'(v) is an arc in G 0 whenever uv is an arc in G. A homomorphism of G to G 0 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 0 . The T -preserving oriented chromatic number ~ T (G) of an oriented graph G is the minimum number of vertices in an oriented graph G 0 such that there exists a T -preserving homomorphism of G to G 0 . 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 sucient 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 homomorphisms, Oriented Graphs. 1