Аннотация:
В 1940 г. в попытках решить проблему четырех красок Лебег дал приближенное описание окрестностей 55-вершин в классе P5P533-многогранников с минимальной степенью 55. Это описание зависит от 3232 главных параметров. Пока получено очень мало точных верхних оценок этих параметров даже для ограниченных подклассов в P5P5.
Для данного 33-многогранника PP через h(P)h(P) обозначим минимум максимальных степеней (высоту) вершин окрестности 55-вершин (младших 55-звезд) в PP.
В 1996 г. Йендроль и Мадараш показали, что если многогранник PP в P5P5 допускает 55-вершины, смежные с четырьмя 55-вершинами (называемыми младшими(5,5,5,5,∞)(5,5,5,5,∞)-звездами), то h(P)h(P) может быть неограниченно большой.
Для каждого P∗P∗ в P5P5 без вершин степеней от 66 до 88 и без младших (5,5,5,5,∞)(5,5,5,5,∞)-звезд из теоремы Лебега следует, что h(P∗)⩽17.
Доказано, в частности, что каждый такой многогранник P∗ удовлетворяет неравенству h(P∗)⩽12, где оценка 12 точна. Этот результат неулучшаем в том смысле, что если одна из степеней в {6,7,8} разрешается, но при этом другие две запрещены, то высота младших 5-звезд в P5, при отсутствии младших (5,5,5,5,∞)-звезд, может достигать 15, 17 или 14 соответственно.
Образец цитирования:
О. В. Бородин, А. О. Иванова, Д. В. Никифоров, “Низкие и легкие 5-звезды в 3-многогранниках с минимальной степенью 5 при наличии запретов на степени старших вершин”, Сиб. матем. журн., 58:4 (2017), 771–778; Siberian Math. J., 58:4 (2017), 600–605
O. V. Borodin, A. O. Ivanova, E. I. Vasil'eva, “Light minor 5-stars in 3-polytopes with minimum degree 5 and no 6-vertices”, Discuss. Math. Graph Theory, 40:4 (2020), 985–994
O. V. Borodin, M. A. Bykov, A. O. Ivanova, “Low 5-stars at 5-vertices in 3-polytopes with minimum degree 5 and no vertices of degree from 7 to 9”, Discuss. Math. Graph Theory, 40:4 (2020), 1025–1033
О. В. Бородин, А. О. Иванова, “Легкие младшие $5$-звезды в $3$-многогранниках с минимальной степенью $5$”, Сиб. матем. журн., 60:2 (2019), 351–359; O. V. Borodin, A. O. Ivanova, “Light minor $5$-stars in $3$-polytopes with minimum degree $5$”, Siberian Math. J., 60:2 (2019), 272–278
Ya. Li, M. Rao, T. Wang, “Minor stars in plane graphs with minimum degree five”, Discret Appl. Math., 257 (2019), 233–242
O.V. Borodin, A.O. Ivanova, O.N. Kazak, “Describing the neighborhoods of 5-vertices in 3-polytopes with minimum degree 5 and no vertices of degree from 6 to 8”, Discrete Mathematics, 342:8 (2019), 2439
O. V. Borodin, A. O. Ivanova, “Light 3-stars in sparse plane graphs”, Сиб. электрон. матем. изв., 15 (2018), 1344–1352
O.V. Borodin, A.O. Ivanova, O.N. Kazak, E.I. Vasil'eva, “Heights of minor 5-stars in 3-polytopes with minimum degree 5 and no vertices of degree 6 and 7”, Discrete Mathematics, 341:3 (2018), 825