O.V. Borodin, M.A. Bykov, A.O. Ivanova
Low 5-stars at 5-vertices in 3-polytopes with minimum degree 5 and no vertices of degree from 7 to 9
Discussiones Mathematicae Graph Theory
Received 18.12.2017, Revised 25.06.2018, Accepted 25.06.2018, doi: 10.7151/dmgt.2159

In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class \bf P5 of 3-polytopes with minimum degree 5. Given a 3-polytope P, by h5(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 \bf P5 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 h5(P) can be arbitrarily large. Therefore, we consider the subclass \bf P*5 of 3-polytopes in \bf P5 that avoid (5,5,6,6,∞)-vertices. For each P* in \bf P*5 without vertices of degree from 7 to 9, it follows from Lebesgue's Theorem that h5(P*)\le 17. Recently, this bound was lowered by Borodin, Ivanova, and Kazak to the sharp bound h5(P*)\le 15 assuming the absence of vertices of degree from 7 to 11 in P*. In this note, we extend the bound h5(P*)\le 15 to all P*s without vertices of degree from 7 to 9.
planar map, planar graph, 3-polytope, structural properties, 5-star, weight, height