Low and light 5-stars in 3-polytopes with minimum degree 5 and restrictions on the degrees of major vertices
- Авторлар: Borodin O.1, Ivanova A.1, Nikiforov D.1
-
Мекемелер:
- Sobolev Institute of Mathematics
- Шығарылым: Том 58, № 4 (2017)
- Беттер: 600-605
- Бөлім: Article
- URL: https://journals.rcsi.science/0037-4466/article/view/171291
- DOI: https://doi.org/10.1134/S003744661704005X
- ID: 171291
Дәйексөз келтіру
Аннотация
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 P5 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 P5. 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 P5 is allowed to have a 5-vertex adjacent to four 5-vertices (called a minor (5, 5, 5, 5,∞)-star), then h(P) can be arbitrarily large. For each P* in P5 with neither vertices of the degree from 6 to 8 nor minor (5, 5, 5, 5,∞)-star, it follows from Lebesgue’s Theorem that h(P*) ≤ 17. We prove in particular that every such polytope P* satisfies h(P*) ≤ 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 P5 under the absence of minor (5, 5, 5, 5,∞)-stars can reach 15, 17, or 14, respectively.
Негізгі сөздер
Авторлар туралы
O. Borodin
Sobolev Institute of Mathematics
Хат алмасуға жауапты Автор.
Email: brdnoleg@math.nsc.ru
Ресей, Novosibirsk
A. Ivanova
Sobolev Institute of Mathematics
Email: brdnoleg@math.nsc.ru
Ресей, Novosibirsk
D. Nikiforov
Sobolev Institute of Mathematics
Email: brdnoleg@math.nsc.ru
Ресей, Novosibirsk