Low 5-Stars at 5-Vertices in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree from 7 to 9

Borodin, Oleg V. ; Bykov, Mikhail A. ; Ivanova, Anna O.

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 1025-1033.

Résumé

In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P_5 of 3-polytopes with minimum degree 5. Given a 3-polytope P, by h_5(P) we denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in P. Recently, Borodin, Ivanova and Jensen showed that if a polytope P in P_5 is allowed to have a 5-vertex adjacent to two 5-vertices and two more vertices of degree at most 6, called a (5, 5, 6, 6, ∞)-vertex, then h_5(P) can be arbitrarily large. Therefore, we consider the subclass P_5^∗ of 3-polytopes in P_5 that avoid (5, 5, 6, 6, ∞)-vertices. For each P^∗ in P_5^∗ without vertices of degree from 7 to 9, it follows from Lebesgue’s Theorem that h_5(P^∗) ≤ 17. Recently, this bound was lowered by Borodin, Ivanova, and Kazak to the sharp bound h_5(P^∗) ≤ 15 assuming the absence of vertices of degree from 7 to 11 in P^∗. In this note, we extend the bound h_5(P^∗) ≤ 15 to all P^∗s without vertices of degree from 7 to 9.

Détail

Keywords: planar map, planar graph, 3-polytope, structural properties, 5-star, weight, height

Bibliographie

[1] O.V. Borodin, Structural properties of planar maps with the minimal degree 5, Math. Nachr. 158 (1992) 109–117. doi:10.1002/mana.19921580108

[2] O.V. Borodin and A.O. Ivanova, Describing 4 -stars at 5 -vertices in normal plane maps with minimum degree 5, Discrete Math. 313 (2013) 1710–1714. doi:10.1016/j.disc.2013.04.025

[3] O.V. Borodin and A.O. Ivanova, Light neighborhoods of 5-vertices in 3-polytopes with minimum degree 5, Sib.Èlektron. Mat. Izv. 13 (2016) 584–591. doi:10.17377/semi.2016.13.045

[4] O.V. Borodin and A.O. Ivanova, Light and low 5 -stars in normal plane maps with minimum degree 5, Sib. Math. J. 57 (2016) 470–475. doi:10.1134/S0037446616030071

[5] O.V. Borodin, A.O. Ivanova and T.R. Jensen, 5 -stars of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory 34 (2014) 539–546. doi:10.7151/dmgt.1748

[6] O.V. Borodin, A.O. Ivanova and O.N. Kazak, Describing neighborhoods of 5 -vertices in 3-polytopes with minimum degree 5 and without vertices of degrees from 7 to 11, Discuss. Math. Graph Theory 38 (2018) 615–625. doi:10.7151/dmgt.2024

[7] O.V. Borodin, A.O. Ivanova, O.N. Kazak and E.I. Vasil’eva, Heights of minor 5 -stars in 3-polytopes with minimum degree 5 and no vertices of degree 6 and 7, Discrete Math. 341 (2018) 825–829. doi:10.1016/j.disc.2017.11.021

[8] O.V. Borodin, A.O. Ivanova and D.V. Nikiforov, Low minor 5 -stars in 3-polytopes with minimum degree 5 and no 6 -vertices, Discrete Math. 340 (2017) 1612–1616. doi:10.1016/j.disc.2017.03.002

[9] O.V. Borodin, A.O. Ivanova and D.V. Nikiforov, Low and light 5-stars in 3-polytopes with minimum degree 5 and restrictions on the degrees of major vertices, Sib. Math. J. 58 (2017) 600–605. doi:10.1134/S003744661704005X

[10] O.V. Borodin and D.R. Woodall, Short cycles of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory 18 (1998) 159–164. doi:10.7151/dmgt.1071

[11] P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225–236. doi:10.2307/2370527

[12] S. Jendrol’ and T. Madaras, On light subgraphs in plane graphs of minimum degree five, Discuss. Math. Graph Theory 16 (1996) 207–217. doi:10.7151/dmgt.1035

[13] H. Lebesgue, Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19 (9) (1940) 27–43.

[14] E. Steinitz, Polyeder und Raumeinteilungen, in: Enzykl. Math. Wiss. (Geometrie), 3 (1922) 1–139.

[15] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413–426. doi:10.1007/BF01444968