Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph; coloring; homomorphism
graph; coloring; homomorphism
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.
References:
[1] Albertson M., Berman D.: An acyclic analogue to Heawood's theorem. Glasgow Math. J. 19 (1978), 163-166. MR 0485490 | Zbl 0378.05030
[2] Alon N., McDiarmid C., Read B.: Acyclic colorings of graphs. Random Structures and Algorithms 2 (1991), 277-289. MR 1109695
[3] Borodin O.V.: On acyclic colorings of planar graphs. Discrete Math. 25 (1979), 211-236. MR 0534939 | Zbl 0406.05031
[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
[5] Dirac G.A.: Some theorems on abstract graphs. Proc. London. Math. Soc. 2 (1952), 69-81. MR 0047308 | Zbl 0047.17001
[6] Häggkvist R., Hell P.: On $A$-mote universal graphs. European J. Combin. 13 (1993), 23-27. MR 1197472
[7] Hell P., Nešetřil J.: On the complexity of $H$-coloring. J. Combin. Theory Series B 48 (1990), 92-110. MR 1047555
[8] Hell P., Nešetřil J., Zhu X.: Duality theorems and polynomial tree-coloring. Trans. Amer. Math. Soc., to appear.
[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
[10] Jensen T.R., Toft B.: Graph Coloring Problems. Wiley Interscience, 1995. MR 1304254 | Zbl 0855.05054
[11] Kostochka A.V., Mel'nikov L.S.: Note to the paper of Grünbaum on acyclic colorings. Discrete Math. 14 (1976), 403-406. MR 0404037 | Zbl 0318.05103
[12] Kostochka A.V., Sopena E., Zhu X.: Acyclic and oriented chromatic numbers of graphs. preprint 95-087, Univ. Bielefeld, 1995. MR 1437294 | Zbl 0873.05044
[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. MR 0607911 | Zbl 0466.05034
[14] Nash-Williams C.St.J.A.: Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12. MR 0161333 | Zbl 0119.38805
[15] Nešetřil J.: Homomorphisms of derivative graphs. Discrete Math. 1 -3 (1971), 257-268. MR 0300939
[16] Nešetřil J., Raspaud A., Sopena E.: Colorings and girth of oriented planar graphs. Research Report 1084-95, Univ. Bordeaux I, 1995.
[17] Nešetřil J., Zhu X.: On bounded treewidth duality of graph homomorphisms. J. Graph Theory, to appear. MR 1408343
[18] Raspaud A., Sopena E.: Good and semi-strong colorings of oriented planar graphs. Inf. Processing Letters 51 (1994), 171-174. MR 1294309 | Zbl 0806.05031
[19] Sopena E.: The chromatic number of oriented graphs. Research Report 1083-95, Univ. Bordeaux I, 1995. Zbl 0874.05026
[20] Thomas R.: Personal communication. 1995.
Search
Partner of
