| Title:
|
$T$-preserving homomorphisms of oriented graphs (English) |
| Author:
|
Nešetřil, J. |
| Author:
|
Sopena, E. |
| Author:
|
Vignal, L. |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
38 |
| Issue:
|
1 |
| Year:
|
1997 |
| Pages:
|
125-136 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graph |
| Keyword:
|
coloring |
| Keyword:
|
homomorphism |
| MSC:
|
05C15 |
| MSC:
|
05C20 |
| idZBL:
|
Zbl 0886.05062 |
| idMR:
|
MR1455476 |
| . |
| Date available:
|
2009-01-08T18:29:33Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118908 |
| . |
| Reference:
|
[1] Albertson M., Berman D.: An acyclic analogue to Heawood's theorem.Glasgow Math. J. 19 (1978), 163-166. Zbl 0378.05030, MR 0485490 |
| Reference:
|
[2] Alon N., McDiarmid C., Read B.: Acyclic colorings of graphs.Random Structures and Algorithms 2 (1991), 277-289. MR 1109695 |
| Reference:
|
[3] Borodin O.V.: On acyclic colorings of planar graphs.Discrete Math. 25 (1979), 211-236. Zbl 0406.05031, MR 0534939 |
| Reference:
|
[4] Borodin O.V., Kostochka A.V., Nešetřil J., Raspaud A., Sopena E.: On the maximum average degree and the oriented chromatic number of a graph.preprint, 1995. MR 1665387 |
| Reference:
|
[5] Dirac G.A.: Some theorems on abstract graphs.Proc. London. Math. Soc. 2 (1952), 69-81. Zbl 0047.17001, MR 0047308 |
| Reference:
|
[6] Häggkvist R., Hell P.: On $A$-mote universal graphs.European J. Combin. 13 (1993), 23-27. MR 1197472 |
| Reference:
|
[7] Hell P., Nešetřil J.: On the complexity of $H$-coloring.J. Combin. Theory Series B 48 (1990), 92-110. MR 1047555 |
| Reference:
|
[8] Hell P., Nešetřil J., Zhu X.: Duality theorems and polynomial tree-coloring.Trans. Amer. Math. Soc., to appear. |
| Reference:
|
[9] Hell P., Nešetřil J., Zhu X.: Duality of graph homomorphisms.Combinatorics, Paul Erdös is eighty, Vol. 2, Bolyai Society Mathematical Studies, 1993. MR 1395863 |
| Reference:
|
[10] Jensen T.R., Toft B.: Graph Coloring Problems.Wiley Interscience, 1995. Zbl 0855.05054, MR 1304254 |
| Reference:
|
[11] Kostochka A.V., Mel'nikov L.S.: Note to the paper of Grünbaum on acyclic colorings.Discrete Math. 14 (1976), 403-406. Zbl 0318.05103, MR 0404037 |
| Reference:
|
[12] Kostochka A.V., Sopena E., Zhu X.: Acyclic and oriented chromatic numbers of graphs.preprint 95-087, Univ. Bielefeld, 1995. Zbl 0873.05044, MR 1437294 |
| Reference:
|
[13] Maurer H.A., Salomaa A., Wood D.: Colorings and interpretations: a connection between graphs and grammar forms.Discrete Applied Math. 3 (1981), 119-135. Zbl 0466.05034, MR 0607911 |
| Reference:
|
[14] Nash-Williams C.St.J.A.: Decomposition of finite graphs into forests.J. London Math. Soc. 39 (1964), 12. Zbl 0119.38805, MR 0161333 |
| Reference:
|
[15] Nešetřil J.: Homomorphisms of derivative graphs.Discrete Math. 1 -3 (1971), 257-268. MR 0300939 |
| Reference:
|
[16] Nešetřil J., Raspaud A., Sopena E.: Colorings and girth of oriented planar graphs.Research Report 1084-95, Univ. Bordeaux I, 1995. |
| Reference:
|
[17] Nešetřil J., Zhu X.: On bounded treewidth duality of graph homomorphisms.J. Graph Theory, to appear. MR 1408343 |
| Reference:
|
[18] Raspaud A., Sopena E.: Good and semi-strong colorings of oriented planar graphs.Inf. Processing Letters 51 (1994), 171-174. Zbl 0806.05031, MR 1294309 |
| Reference:
|
[19] Sopena E.: The chromatic number of oriented graphs.Research Report 1083-95, Univ. Bordeaux I, 1995. Zbl 0874.05026 |
| Reference:
|
[20] Thomas R.: Personal communication.1995. |
| . |
