Эта публикация цитируется в
7 статьях
Дискретная математика и математическая кибернетика
Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$
O. V. Borodina,
A. O. Ivanovab a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Ammosov North-Eastern Federal University, str. Kulakovskogo, 48,
677000, Yakutsk, Russia
Аннотация:
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.
Ключевые слова:
planar map, planar graph,
$3$-polytope, structural properties, height, weight.
Поступила 18 мая 2016 г., опубликована
30 июня 2016 г.
Язык публикации: английский
DOI:
10.17377/semi.2016.13.045