Full entry |
PDF
(0.2 MB)
Feedback

graph; coloring; homomorphism

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.