$T$-preserving homomorphisms of oriented graphs

Nešetřil, J. ; Sopena, E. ; Vignal, L.

Commentationes Mathematicae Universitatis Carolinae, Tome 38 (1997) no. 1, pp. 125-136

Résumé

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.

Détail

Classification : 05C15, 05C20
Keywords: graph; coloring; homomorphism