zbMATH — the first resource for mathematics

Acyclic colouring of 1-planar graphs. (English) Zbl 0996.05053
See the review of the Russian original [Diskretn. Anal. Issled. Oper., Ser. 1 6, No. 4, 20-35 (1999; Zbl 0931.05032)].

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Algor, I.; Alon, N., The star arboricity of graphs, Discrete math., 75, 11-22, (1989) · Zbl 0684.05033
[2] Alon, N.; Marshall, T.H., Homomorphisms of edge-colored graphs and Coxeter groups, J. algebraic combin., 2, 277-289, (1991)
[3] Alon, N.; Mohar, B.; Sanders, D.P., On acyclic colorings of graphs on surfaces, Isr. J. math., 94, 273-283, (1996) · Zbl 0857.05033
[4] Archdeacon, D., Coupled coloring of planar maps, Congr. numer., 39, 89-94, (1986)
[5] Borodin, O.V., On acyclic colorings of planar graphs, Discrete math., 25, 211-236, (1979) · Zbl 0406.05031
[6] O.V. Borodin, Solution of Ringel’s problems on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs, Diskret. Analiz 41 1984 12-26 (in Russian). · Zbl 0565.05027
[7] Borodin, O.V., A new proof of six color theorem, J. graph theory, 19, 507-521, (1995) · Zbl 0826.05027
[8] O.V. Borodin, A.V. Kostochka, D.R. Woodall, Acyclic colorings of planar graphs with large girth, J. London Math. Soc., accepted for publication. · Zbl 0940.05032
[9] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. math., 1, 390-408, (1973) · Zbl 0265.05103
[10] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley New York · Zbl 0971.05046
[11] Kostochka, A.V.; Mel’nikov, L.S., Note to the paper of grünbaum on acyclic colorings, Discrete math., 14, 403-406, (1976) · Zbl 0318.05103
[12] J. Nešetřil, A. Raspaud, Colored Homomorphisms of colored mixed graphs KAM Series No. 98-376, Department of Applied Mathematics, Charles University, Prague).
[13] Raspaud, A.; Sopena, E., Good and semi-strong colorings of oriented planar graphs, Inform. process. lett., 51, 171-174, (1994) · Zbl 0806.05031
[14] Ringel, G., Ein sechsfarbenproblem auf der kugel, Abh. math. sem. univ. Hamburg, 29, 107-117, (1965) · Zbl 0132.20701
[15] G. Ringel, A Six Color Problem on the sphere, Theory of Graphs: Proceedings of the Colloquium, Tihany, 1966, Academic Press, New York, 1968, pp. 265-269.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.