$T$-preserving homomorphisms of oriented graphs

Nešetřil, Jaroslav, Sopena, Eric, and Vignal, Laurence. "$T$-preserving homomorphisms of oriented graphs." Commentationes Mathematicae Universitatis Carolinae 38.1 (1997): 125-136. <http://eudml.org/doc/248064>.

@article{Nešetřil1997,
abstract = {A homomorphism of an oriented graph $G=(V,A)$ to an oriented graph $G^\{\prime \}=(V^\{\prime \},A^\{\prime \})$ is a mapping $\varphi $ from $V$ to $V^\{\prime \}$ such that $\varphi (u)\varphi (v)$ is an arc in $G^\{\prime \}$ whenever $uv$ is an arc in $G$. A homomorphism of $G$ to $G^\{\prime \}$ 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^\{\prime \}$. 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^\{\prime \}$ such that there exists a $T$-preserving homomorphism of $G$ to $G^\{\prime \}$. 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.},
author = {Nešetřil, Jaroslav, Sopena, Eric, Vignal, Laurence},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph; coloring; homomorphism; graph; coloring; homomorphism; chromatic number},
language = {eng},
number = {1},
pages = {125-136},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {$T$-preserving homomorphisms of oriented graphs},
url = {http://eudml.org/doc/248064},
volume = {38},
year = {1997},
}

TY - JOUR
AU - Nešetřil, Jaroslav
AU - Sopena, Eric
AU - Vignal, Laurence
TI - $T$-preserving homomorphisms of oriented graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1997
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 38
IS - 1
SP - 125
EP - 136
AB - A homomorphism of an oriented graph $G=(V,A)$ to an oriented graph $G^{\prime }=(V^{\prime },A^{\prime })$ is a mapping $\varphi $ from $V$ to $V^{\prime }$ such that $\varphi (u)\varphi (v)$ is an arc in $G^{\prime }$ whenever $uv$ is an arc in $G$. A homomorphism of $G$ to $G^{\prime }$ 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^{\prime }$. 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^{\prime }$ such that there exists a $T$-preserving homomorphism of $G$ to $G^{\prime }$. 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.
LA - eng
KW - graph; coloring; homomorphism; graph; coloring; homomorphism; chromatic number
UR - http://eudml.org/doc/248064
ER -