zbMATH — the first resource for mathematics

Simultaneous coloring of edges and faces of plane graphs. (English) Zbl 0807.05029
The edge-and-face chromatic number \(\chi_{\text{ef}}(G)\) of a plane graph \(G\) is the least number of colors required to color the edges and faces of \(G\) such that every two adjacent or incident of them receive different colors. It is proved that if \(G\) is a plane graph with maximum degree at least 10 then \(\chi_{\text{ef}}(G)\leq \Delta(G)+1\), the bound being sharp. The proof is based on some new generalizations of Kotzig’s Theorem on the minimal weight of edges in plane graphs. It is also proved that if \(G\) is a plane graph without separating triangles and \(\Delta(G)\leq 7\) then \(\chi_{\text{ef}}(G)\leq 10\).
Reviewer: M.Frick (Pretoria)

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Appel, K.; Haken, W., Every planar map is four colorable, Bull. amer. math. soc., 82, 711-712, (1976) · Zbl 0331.05106
[2] Behzad, M.; Chartrand, G.; Cooper, J., The colour numbers of complete graphs, J. London math. soc., 42, 226-228, (1967) · Zbl 0152.41203
[3] Borodin, O.V., Solution of Ringel’s problems of the face and vertex coloring of plane graphs and coloring of 1-planar graphs, Metody diskret. analiza, 41, 12-26, (1984), (in Russian) · Zbl 0565.05027
[4] Borodin, O.V., Consistent colorings of graphs on the sphere, Metody diskret. analiza, 45, 21-27, (1987), (in Russian) · Zbl 0643.05029
[5] Borodin, O.V., On the total coloring of planar graphs, J. reine angew. math., 394, 180-185, (1989) · Zbl 0653.05029
[6] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, (), 125-157, Proc. West. Coast Conf. Combin.
[7] Fiamchik, J., Simultaneous colouring of 4-valent maps, Mat. čas., 21, 9-13, (1971) · Zbl 0213.50704
[8] Jucovič, E., On a problem in map colouring, Mat. čas., 19, 225-227, (1969) · Zbl 0187.21001
[9] Kostochka, A.V., Exact upper bound for the total chromatic number of multigraphs, 24th int wiss. koll. TH ilmenau, 33-36, (1979), (in Russian)
[10] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. čas., 5, 101-103, (1955), (in Russian)
[11] Kronk, H.; Mitchem, J., A seven-color theorem on the sphere, Discrete math., 5, 253-260, (1973) · Zbl 0256.05106
[12] Recent advances in graph theory, ()
[13] Ringel, G., Ein sechsfarbenproblem auf der kugel, Abh. math. sem. univ. Hamburg, 29, 107-117, (1965) · Zbl 0132.20701
[14] Vizing, V.G., On the bound for the chromatic number of p-graphs, Diskret. analiz, 3, 25-30, (1964), (in Russian) · Zbl 1249.05144
[15] Vizing, V.G., Some open problems in graph theory, Uspehi mat. nauk., 23, 117-134, (1968), (in Russian) · Zbl 0177.52301
[16] Vizing, V.G., Coloring the vertices of a graph with assigned colors, Metody diskret. analiza, 29, 3-10, (1976), (in Russian)
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.