×

The vertex-face weight of edges in 3-polytopes. (English. Russian original) Zbl 1331.52018

Sib. Math. J. 56, No. 2, 275-284 (2015); translation from Sib. Mat. Zh. 56, No. 2, 338-350 (2015).
Summary: The weight \(w(e)\) of an edge \(e\) in a 3-polytope is the maximum degree-sum of the two vertices and two faces incident with \(e\). In 1940, Lebesgue proved that each 3-polytope without the so-called pyramidal edges has an edge \(e\) with \(w(e) \leq 21\). In 1995, this upper bound was improved to 20 by Avgustinovich and Borodin. Note that each edge of the \(n\)-pyramid is pyramidal and has weight \(n + 9\). Recently, we constructed a 3-polytope without pyramidal edges satisfying \(w(e) \geq 18\) for each \(e\). The purpose of this paper is to prove that each 3-polytope without pyramidal edges has an edge \(e\) with \(w(e) \leq 18\). In other terms, this means that each plane quadrangulation without a face incident with three vertices of degree 3 has a face with the vertex degree-sum at most 18, which is tight.

MSC:

52B10 Three-dimensional polytopes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Steinitz E., “Polyheder und Raumeinteilungen,” Enzykl. Math. Wiss. (Geometrie), 3, No. 3AB12, 1-139 (1922).
[2] Lebesgue H., “Quelques conséquences simples de la formule d’Euler,” J. Math. Pures Appl., 19, 27-43 (1940). · Zbl 0024.28701
[3] Avgustinovich S. V. and Borodin O. V., “Neighborhoods of edges in normal maps,” Diskret. Anal. Issled. Oper., 2, No. 3, 3-9 (1995). (English translation: Oper. Res. Discrete Anal., 391, 17-22 (1997).) · Zbl 0856.05031
[4] Borodin O. V. and Ivanova A. O., “The height of edge in 3-polytope,” Siberian Elektron. Mat. Izv., 11, 457-463 (2014). · Zbl 1326.05060
[5] Borodin O. V., “Colorings of plane graphs: a survey,” Discrete Math., 313, No. 4, 517-539 (2013). · Zbl 1259.05042 · doi:10.1016/j.disc.2012.11.011
[6] Ore, O.; Plummer, M. D.; Tutte, W. T. (ed.), Cyclic coloration of plane graphs, 287-293 (1969), New York
[7] Plummer M. D. and Toft B., “Cyclic coloration of 3-polytopes,” J. Graph Theory, 11, 507-515 (1987). · Zbl 0655.05030 · doi:10.1002/jgt.3190110407
[8] Kotzig A., “From the theory of Eulerian polyhedra,” Mat. Čas., 13, 20-34 (1963). · Zbl 0134.19601
[9] Borodin O. V., “Solving the Kotzig and Grünbaum problems on the separability of a cycle in planar graphs,” Mat. Zametki, 46, No. 5, 9-12 (1989). (English translation: Math. Notes, 46, No. 5-6, 835-837 (1989).) · Zbl 0694.05027
[10] Grünbaum B., “Polytopal graphs,” in: Studies in Graph Theory (ed D. R. Fulkerson), Washington, D.C., Math. Assoc. Amer., Vol. 12, 1975, pp. 201-224 (MAA Stud. Math.). · Zbl 0323.05104
[11] Plummer, M. D., On the cyclic connectivity of planar graphs, 235-242 (1972), Berlin · Zbl 0247.05113 · doi:10.1007/BFb0067376
[12] Kotzig A., “Extremal polyhedral graphs,” Ann. New York Acad. Sci., 319, 569-570 (1979).
[13] Borodin O. V., “Minimal weight of a face in planar triangulations without 4-vertices,” Mat. Zametki, 51, No. 1, 16-19 (1992). (English translation: Math. Notes, 51, No. 1-2, 11-13 (1992).) · Zbl 0755.05091
[14] Borodin O. V., “Triangulated 3-polytopes with restricted minimal weight of faces,” Discrete Math., 186, 281-285 (1998). · Zbl 0956.52010 · doi:10.1016/S0012-365X(97)00240-9
[15] Horňák M. and Jendrol’ S., “Unavoidable sets of face types for planar maps,” Discus. Math. Graph Theory, 16, No. 2, 123-142 (1996). · Zbl 0877.05048 · doi:10.7151/dmgt.1028
[16] Borodin O. V. and Woodall D. R., “The weight of faces in plane maps,” Mat. Zametki, 64, No. 5, 648-657 (1998). (English translation: Math. Notes, 64, No. 5, 562-570 (1998).) · Zbl 0958.52015 · doi:10.4213/mzm1441
[17] Jendrol’ S. and Voss H.-J., “Light subgraphs of graphs embedded in the plane and in the projective plane: a survey,” Discrete Math., 313, No. 4, 406-421 (2013). · Zbl 1259.05045 · doi:10.1016/j.disc.2012.11.007
[18] Borodin O. V., “Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps,” Diskret. Mat., 3, No. 4, 24-27 (1991). · Zbl 0742.05034
[19] Borodin O. V. and Loparev D. V., “The height of small faces in planar normal maps,” Diskretn. Anal. Issled. Oper., 5, No. 4, 6-17 (1998). · Zbl 0913.05039
[20] Borodin O. V. and Woodall D. R., “Cyclic degrees of 3-polytopes,” Graphs Comb., 15, 267-277 (1999). · Zbl 0930.05055 · doi:10.1007/s003730050060
[21] Ferencová B. and Madaras T., “On the structure of polyhedral graphs with prescribed edge and dual edge weight,” Acta Univ. M. Belii Math., 12, 13-18 (2005). · Zbl 1103.05026
[22] Ferencová B. and Madaras T., “Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight,” Discrete Math., 310, 1661-1675 (2010). · Zbl 1222.05217 · doi:10.1016/j.disc.2009.11.027
[23] Jendrol’ S., “Triangles with restricted degrees of their boundary vertices in plane triangulations,” Discrete Math., 196, 177-196 (1999). · Zbl 0934.05044 · doi:10.1016/S0012-365X(98)00172-1
[24] Kotzig A., “Contribution to the theory of Eulerian polyhedra,” Mat. Fyz. Casopis, 5, 101-113 (1955).
[25] Madaras T. and Škrekovski R., “Heavy paths, light stars, and big melons,” Discrete Math., 286, 115-131 (2004). · Zbl 1053.05035 · doi:10.1016/j.disc.2003.11.052
[26] Madaras T. and Soták R., “The 10-cycle is light in the family of all plane triangulations with minimum degree five,” Tatra Mt. Math. Publ., 18, 35-56 (1999). · Zbl 0951.05031
[27] Madaras T., Škrekovski R., and Voss H.-J., “The 7-cycle C7 is light in the family of planar graphs with minimum degree 5,” Discrete Math., 307, 1430-1435 (2007). · Zbl 1115.05022 · doi:10.1016/j.disc.2005.11.080
[28] Mohar B., Škrekovski R., Voss H.-J., “Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9,” J. Graph Theory, 44, 261-295 (2003). · Zbl 1031.05075 · doi:10.1002/jgt.10144
[29] Wernicke P., “Über den Kartographischen Vierfarbensatz,” Math. Ann., 58, 413-426 (1904). · JFM 35.0511.01 · doi:10.1007/BF01444968
[30] Borodin O. V., “Strengthening Lebesgue’s theorem on the structure of the minor faces in convex polyhedra,” Diskretn. Anal. Issled. Oper. Ser. 1, 9, No. 3, 29-39 (2002). · Zbl 1015.52008
[31] Borodin O. V. and Ivanova A. O., “Describing 3-faces in normal plane maps with minimum degree 4,” Discrete Math., 313, No. 23, 2841-2847 (2013). · Zbl 1281.05054 · doi:10.1016/j.disc.2013.08.028
[32] Borodin O. V., Ivanova A. O., and Kostochka A. V., “Describing faces in plane triangulations,” Discrete Math., 319, 47-61 (2014). · Zbl 1280.05027 · doi:10.1016/j.disc.2013.11.021
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.