Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree~$5$

O. V. Borodin ; A. O. Ivanova

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 584-591

Résumé

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 $\mathbf{P}_5$ of $3$-polytopes with minimum degree $5$. Given a $3$-polytope $P$, by $w(P)$ ($h(P)$) we denote the minimum degree-sum (minimum of the maximum degrees) of the neighborhoods of $5$-vertices in $P$. A $5^*$-vertex is a $5$-vertex adjacent to four $5$-vertices. It is known that if a polytope $P$ in $\mathbf{P}_5$ has a $5^*$-vertex, then $h(P)$ can be arbitrarily large. For each $P$ without vertices of degrees from $6$ to $9$ and $5^*$-vertices in $\mathbf{P}_5$, it follows from Lebesgue's Theorem that $w(P)\le 44$ and $h(P)\le 14$. In this paper, we prove that every such polytope $P$ satisfies $w(P)\le 42$ and $h(P)\le 12$, where both bounds are tight.

Détail

Keywords: planar map, planar graph, $3$-polytope, structural properties, height, weight.