|
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.
Received: 05.07.2018 Revised: 05.07.2018 Accepted: 17.08.2018
Citation:
O. V. Borodin, A. O. Ivanova, “Light minor $5$-stars in $3$-polytopes with minimum degree $5$”, Sibirsk. Mat. Zh., 60:2 (2019), 351–359; Siberian Math. J., 60:2 (2019), 272–278
Linking options:
https://www.mathnet.ru/eng/smj3079 https://www.mathnet.ru/eng/smj/v60/i2/p351
|
Statistics & downloads: |
Abstract page: | 223 | Full-text PDF : | 33 | References: | 28 | First page: | 3 |
|