RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2019 Volume 60, Number 2, Pages 351–359 (Mi smj3079)

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


 English version:
Siberian Mathematical Journal, 2019, 60:2, 272–278

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024