×

zbMATH — the first resource for mathematics

On the weight of minor faces in triangle-free 3-polytopes. (English) Zbl 1339.05112
Summary: The weight \(w(f)\) of a face \(f\) in a 3-polytope is the degree-sum of vertices incident with \(f\). It follows from H. Lebesgue’s results [J. Math. Pures Appl., IX. Sér. 19, 27–43 (1940; Zbl 0024.28701)] that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with \(w\leq21\) or a 5-face with \(w\leq17\). Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp.
The purpose of this paper is to improve this 21 to 20, which is best possible.

MSC:
05C15 Coloring of graphs and hypergraphs
05C22 Signed and weighted graphs
52B99 Polytopes and polyhedra
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S.V. Avgustinovich and O.V. Borodin, Neighborhoods of edges in normal maps, Diskretn. Anal. Issled. Oper. 2 (1995) 3-9, in Russian. · Zbl 0856.05031
[2] O.V. Borodin, Solution of Kotzig’s and Grünbaum’s problems on the separability of a cycle in a planar graph, Mat. Zametki 46 (1989) 9-12, in Russian.
[3] O.V. Borodin, Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps, Diskret. Mat. 3 (1991) 24-27, in Russian. · Zbl 0742.05034
[4] O.V. Borodin, Minimal weight of a face in plane triangulations without 4-vertices, Mat. Zametki 51 (1992) 16-19, in Russian. · Zbl 0755.05091
[5] O.V. Borodin, Triangulated 3-polytopes with restricted minimal weight of faces, Discrete Math. 186 (1998) 281-285. doi:10.1016/S0012-365X(97)00240-9
[6] O.V. Borodin and D.V. Loparev, The height of small faces in planar normal maps, Diskretn. Anal. Issled. Oper. 5 (1998) 6-17, in Russian. · Zbl 0913.05039
[7] O.V. Borodin and D.R. Woodall, The weight of faces in plane maps, Mat. Zametki 64 (1998) 648-657, in Russian. · Zbl 0958.52015
[8] O.V. Borodin and D.R. Woodall, Cyclic degrees of 3-polytopes, Graphs Combin. 15 (1999) 267-277. · Zbl 0930.05055
[9] O.V. Borodin, An improvement of Lebesgue’s theorem on the structure of minor faces of 3-polytopes, Diskretn. Anal. Issled. Oper. 9 (2002) 29-39, in Russian. · Zbl 1015.52008
[10] O.V. Borodin, Colorings of plane graphs: a survey, Discrete Math. 313 (2013) 517-539. doi:10.1016/j.disc.2012.11.011 · Zbl 1259.05042
[11] O.V. Borodin and A.O. Ivanova, Describing 3-faces in normal plane maps with minimum degree 4, Discrete Math. 313 (2013) 2841-2847. doi:10.1016/j.disc.2013.08.028 · Zbl 1281.05054
[12] O.V. Borodin, A.O. Ivanova and A.V. Kostochka, Describing faces in plane triangulations, Discrete Math. 319 (2014) 47-61. doi:10.1016/j.disc.2013.11.021 · Zbl 1280.05027
[13] O.V. Borodin, A.O. Ivanova and D.R. Woodall, Light C4 and C5 in 3-polytopes with minimum degree 5, Discrete Math. 334 (2014) 63-69. doi:10.1016/j.disc.2014.06.024 · Zbl 1298.05083
[14] O.V. Borodin, A.O. Ivanova and A.V. Kostochka, Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11, Discrete Math. 315-316 (2014) 128-134. doi:10.1016/j.disc.2013.10.021 · Zbl 1278.05080
[15] O.V. Borodin and A.O. Ivanova, The vertex-face weight of edges in 3-polytopes, Sibirsk. Mat. Zh. 56 (2015) 338-350, in Russian. · Zbl 1331.52018
[16] O.V. Borodin and A.O. Ivanova, Every 3-polytope with minimum degree 5 has a 7-cycle with maximum degree at most 15, Sibirsk. Mat. Zh. 56 (2015) 775-789, in Russian. · Zbl 1410.52008
[17] B. Ferencová and T. Madaras, On the structure of polyhedral graphs with prescribed edge and dual edge weight , Acta Univ. M. Belii Ser. Math. 12 (2005) 13-18. · Zbl 1103.05026
[18] B. Ferencová and T. Madaras, Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight , Discrete Math. 310 (2010) 1661-1675. doi:10.1016/j.disc.2009.11.027 · Zbl 1222.05217
[19] B. Grünbaum, Polytopal graphs, in: Studies in Graph Theory, D.R. Fulkerson, Ed., MAA Studies in Mathematics 12 (1975) 201-224.
[20] M. Horňák and S. Jendroľ, Unavoidable sets of face types for planar maps, Discuss. Math. Graph Theory 16 (1996) 123-142. doi:10.7151/dmgt.1028
[21] S. Jendroľ, Triangles with restricted degrees of their boundary vertices in plane triangulations, Discrete Math. 196 (1999) 177-196. doi:10.1016/S0012-365X(98)00172-1
[22] S. Jendroľ and H.-J. Voss, Light subgraphs of graphs embedded in the plane and in the projective plane-a survey, Discrete Math. 313 (2013) 406-421. doi:10.1016/j.disc.2012.11.007
[23] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Čas. 5 (1955) 101-113, in Russian.
[24] A. Kotzig, From the theory of Eulerian polyhedra, Mat. Čas. 13 (1963) 20-34. · Zbl 0134.19601
[25] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569-570.
[26] H. Lebesgue, Quelques conséquences simples de la formule d’Euler , J. Math. Pures Appl. 19 (1940) 27-43. · JFM 66.0736.03
[27] T. Madaras and R. Škrekovski, Heavy paths, light stars, and big melons, Discrete Math. 286 (2004) 115-131. doi:10.1016/j.disc.2013.11.052 · Zbl 1053.05035
[28] T. Madaras and R. Soták, The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five, Tatra Mt. Math. Publ. 18 (1999) 35-56.
[29] T. Madaras, R. Škrekovski and H.-J. Voss, The 7-cycle C7 is light in the family of planar graphs with minimum degree 5, Discrete Math. 307 (2007) 1430-1435. doi:10.1016/j.disc.2005.11.080 · Zbl 1115.05022
[30] B.Mohar, R. Škrekovski and H.-J. Voss, Light subraphs in planar graphs of minimum degree 4 and edge-degree 9, J. Graph Theory 44 (2003) 261-295. doi:10.1002/jgt.10144 · Zbl 1031.05075
[31] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, Recent Progress in Combinatorics, W.T. Tutte, Ed. (Academic Press, New York, 1969) 287-293. · Zbl 0195.25701
[32] M.D. Plummer, On the cyclic connectivity of planar graph, Graph Theory and Application (Springer-Verlag, Berlin, 1972) 235-242.
[33] M.D. Plummer and B. Toft, Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987) 507-515. doi:10.1002/jgt.3190110407 · Zbl 0655.05030
[34] E. Steinitz, Polyheder und Raumeinteilungen, Enzykl. Math. Wiss. (Geometrie) 3AB (1922) 1-139.
[35] P. Wernicke, Über den Kartographischen Vierfarbensatz , Math. Ann. 58 (1904) 413-426. · JFM 35.0511.01
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.