The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. 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.
@article{bwmeta1.element.doi-10_7151_dmgt_1877,
author = {Oleg V. Borodin and Anna O. Ivanova},
title = {On the Weight of Minor Faces in Triangle-Free 3-Polytopes},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {603-619},
zbl = {1339.05112},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1877}
}
Oleg V. Borodin; Anna O. Ivanova. On the Weight of Minor Faces in Triangle-Free 3-Polytopes. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 603-619. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1877/
[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[Crossref]
[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.[Crossref] | 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[Crossref] | 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[Crossref][WoS]
[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[WoS][Crossref] | 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[Crossref] | 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[Crossref] | 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.[WoS] | 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 06501740
[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[WoS][Crossref] | 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[Crossref] | Zbl 0877.05048
[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[Crossref]
[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[Crossref][WoS] | Zbl 1259.05045
[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. | Zbl 0024.28701
[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[Crossref] | 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. | Zbl 0951.05031
[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[Crossref] | 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[Crossref] | 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 [Crossref]
[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. | Zbl 35.0511.01