Low and light 5-stars in 3-polytopes with minimum degree 5 and restrictions on the degrees of major vertices

Abstract

In 1940, in attempts to solve the Four Color Problem, Henry Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P₅ of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. Very few precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P₅. Given a 3-polytope P, denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in P by h(P). Jendrol’ and Madaras in 1996 showed that if a polytope P in P₅ is allowed to have a 5-vertex adjacent to four 5-vertices (called a minor (5, 5, 5, 5,∞)-star), then h(P) can be arbitrarily large. For each P^* in P₅ with neither vertices of the degree from 6 to 8 nor minor (5, 5, 5, 5,∞)-star, it follows from Lebesgue’s Theorem that h(P^*) ≤ 17. We prove in particular that every such polytope P^* satisfies h(P^*) ≤ 12, and this bound is sharp. This result is best possible in the sense that if vertices of one of degrees in {6, 7, 8} are allowed but those of the other two forbidden, then the height of minor 5-stars in P₅ under the absence of minor (5, 5, 5, 5,∞)-stars can reach 15, 17, or 14, respectively.