zbMATH — the first resource for mathematics

Weight of faces in plane maps. (English. Russian original) Zbl 0958.52015
Math. Notes 64, No. 5, 562-570 (1998); translation from Mat. Zametki 64, No. 5, 648-657 (1998).
In his doctoral thesis (1994), O. V. Borodin described the structure of the neighbourhoods (in the combinatorial sense of weights) of edges and faces in several classes of planar graphs (with applications to problems of cyclic and simultaneous colorings). In particular, e.g. the edge neighbourhoods of 3-polytopes could be described in a detailed manner.
In the present paper, the authors investigate the structure of face neighbourhoods of planar graphs. More precisely, they derive exact upper bounds for the minimum weight of minor faces in normal planar maps and for 3-polytopes with specified maximal vertex degree.

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
Full Text: DOI
[1] E. Steinitz, ”Polyheder und Raumeinteilungen,”Enzykl. Math. Wiss. 3 (Geometrie). Part 3AB,12, 1–139 (1922).
[2] H. Lebesgue, ”Quelques conséquences simples de la formule d’Euler,”J. Math. Pures Appl.,9, 27–43 (1940). · Zbl 0024.28701
[3] O. V. Borodin,The Structure and Colourings of Plane Graphs [in Russian], Doctorate thesis in the physico-mathematical sciences, Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk (1994).
[4] O. V. Borodin, ”The structure of edge neighborhoods in plane graphs and the simultaneous coloring of vertices, edges and faces,”Mat. Zametki [Math. Notes],53, No. 5, 35–47 (1993). · Zbl 0795.05048
[5] A. V. Ivanov, ”Semiregular polytopes,” in:Mathematical Encyclopedia [in Russian], Vol. 4, Soviet Encyclopedia, Moscow (1984), p. 463.
[6] A. Kotzig, ”Extremal polyhedral graphs,” in:Proc. 2nd Intern. Conference on Combinatorial Math, New York (1978), pp. 569–570.
[7] O. V. Borodin, ”Minimal weight of face in plane triangulations without 4-vertices,”Mat. Zametki [Math. Notes],51, No. 1, 16–19 (1992). · Zbl 0755.05091
[8] O. V. Borodin, ”Triangulated 3-polytopes with restricted minimal weight of faces,”Discrete Math. (to appear). · Zbl 0956.52010
[9] O. V. Borodin, ”Cyclic degree and cyclic coloring of 3-polytopes,”J. Graph Theory,23, No. 3, 225–231 (1996). · Zbl 0865.05042
[10] M. Hornák and S. Jendrol’, ”Unavoidable sets of face types for planar maps,”Discuss. Math. (to appear).
[11] O. V. Borodin and D. R. Woodall, ”Cyclic degrees of 3-polytopes,”SIAM J. Discrete Math. (to appear). · Zbl 0930.05055
[12] O. V. Borodin, ”Joint extension of Lebesgue’s and Kotzig’s theorem on the combinatorics of plane maps,”Diskret. Mat. [Discrete Math. Appl.],3, No. 4, 24–28 (1991).
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.