Light minor $5$-stars in $3$-polytopes with minimum degree $5$
O. V. Borodin,
A. O. Ivanova Sobolev Institute of Mathematics, Novosibirsk, Russia
Abstract:
Attempting to solve the Four Color Problem in 1940, 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$. This description depends on
$32$ main parameters. Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in
$\mathbf{P}_5$. Given a
$3$-polytope
$P$, by
$w(P)$ denote the minimum of the maximum degree-sum (weight) of the neighborhoods of
$5$-vertices (minor
$5$-stars) in
$P$. In 1996, Jendrol’ and Madaras showed that if a polytope
$P$ in
$\mathbf{P}_5$ is allowed to have a
$5$-vertex adjacent to four
$5$-vertices (called a
minor $(5, 5, 5, 5, \infty)$-
star), then
$w(P)$ can be arbitrarily large. For each
$P^*$ in
$\mathbf{P}_5$ with neither vertices of degree
$6$ and
$7$ nor minor
$(5, 5, 5, 5, \infty)$-star, it follows from Lebesgue's Theorem that
$w(P^*) \leqslant 51$. We prove that every such polytope
$P^*$ satisfies
$w(P^*) \leqslant 42$, which bound is sharp. This result is also best possible in the sense that if
$6$-vertices are allowed but
$7$-vertices forbidden, or vice versa; then the weight of all minor
$5$-stars in
$\mathbf{P}_5$ under the absence of minor
$(5, 5, 5, 5, \infty)$-stars can reach
$43$ or
$44$, respectively.
Keywords:
planar map, planar graph, $3$-polytope, structural properties, $5$-star.
UDC:
519.17
MSC: 35R30 Received: 05.07.2018
Revised: 05.07.2018
Accepted: 17.08.2018
DOI:
10.33048/smzh.2019.60.207