Бородин О. В., Иванова А. О., Никифоров Д. В.
Низкие и легкие 5-звезды в 3-многогранниках с минимальной степенью 5 при наличии запретов на степени старших вершин

В 1940 г. в попытках решить проблему четырех красок Лебег дал приближенное описание окрестностей 5-вершин в классе $\mathbf{P}_5$ 3-многогранников с минимальной степенью 5. Это описание зависит от 32 главных параметров. Пока получено очень мало точных верхних оценок этих параметров даже для ограниченных подклассов в $\mathbf{P}_5$.
Для данного 3-многогранника $P$ через $h$($P$) обозначим минимум максимальных степеней (высоту) вершин окрестности 5-вершин (младших 5-звезд) в $P$.
В 1996 г. Йендроль и Мадараш показали, что если многогранник $P$ в $\mathbf{P}_5$ допускает 5-вершины, смежные с четырьмя 5-вершинами (называемыми младшими (5, 5, 5, 5, $\infty$)-звездами), то $h$($P$) может быть неограниченно большой.
Для каждого $P^{\ast}$ в $\mathbf{P}_5$ без вершин степеней от 6 до 8 и без младших (5, 5, 5, 5,$\infty$)-звезд из теоремы Лебега следует, что $h$($P^{\ast}$) $\le$ 17.
Доказано, в частности, что каждый такой многогранник $P^{\ast}$ удовлетворяет неравенству $h$($P^{\ast}$) $\le$ 12, где оценка 12 точна. Этот результат неулучшаем в том смысле, что если одна из степеней в {6, 7, 8} разрешается, но при этом другие две запрещены, то высота младших 5-звезд в $\mathbf{P}_5$, при отсутствии младших (5, 5, 5, 5, $\infty$)-звезд, может достигать 15, 17 или 14 соответственно.

O. V. Borodin, A. O. Ivanova, D. V. Nikiforov
Low and light 5-stars in 3-polytopes with minimum degree 5 and restrictions on the degrees of major vertices

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. This description depends on 32 main parameters. Very few precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in $\mathbf{P}_5$. Given a 3-polytope $P$, denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in $P$ by $h$($P$). Jendrol’ and Madaras in 1996 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 $h$($P$) can be arbitrarily large. For each $P^{\ast}$ in $\mathbf{P}_5$ with neither vertices of the degree from 6 to 8 nor minor (5, 5, 5, 5, $\infty$)-star, it follows from Lebesgue’s Theorem that $h$($P^{\ast}$) $\le$ 17. We prove in particular that every such polytope $P^{\ast}$ satisfies $h$($P^{\ast}$) $\le$ 12, and this bound is sharp. This result is best possible in the sense that if vertices of one of degrees in {6, 7, 8} are allowed but those of the other two forbidden, then the height of minor 5-stars in $\mathbf{P}_5$ under the absence of minor (5, 5, 5, 5, $\infty$)-stars can reach 15, 17, or 14, respectively.

DOI 10.17377/smzh.2017.58.405
Ключевые слова: плоская карта, плоский граф, 3-многогранник, структурные свойства, 5-звезда, высота, вес.

Полный текст статьи / Full texts:

• PDF file