Abstract
Lebesgue proved in 1940 that each 3-polytope with minimum degree 5 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences
(6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11)
(5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17)
(5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6,∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11)
(5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13).
We prove that each 3-polytope with minimum degree 5 without vertices of degree from 7 to 10 contains a 5-vertex whose set of degrees of its neighbors is majorized by one of the following sequences: (5, 6, 6, 5, ∞), (5, 6, 6, 6, 15), and (6, 6, 6, 6, 6), where all parameters are tight.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Steinitz E., “Polyeder und Raumeinteilungen,” Enzykl. Math. Wiss. (Geometrie), vol. 3AB, no. 12, 1–139 (1922).
Wernicke P., “Über den kartographischen Vierfarbensatz,” Math. Ann., Bd 58, 413–426 (1904).
Franklin Ph., “The four color problem,” Amer. J. Math., vol. 44, no. 3, 225–236 (1922).
Borodin O. V. and Ivanova A. O., “An analogue of Franklin’s theorem,” Discrete Math., vol. 339, no. 10, 2553–2556 (2016).
Lebesgue H., “Quelques conséquences simples de la formule d’Euler,” J. Math. Pures Appl., vol. 19, 27–43 (1940).
Borodin O. V., “Colorings of plane graphs: a survey,” Discrete Math., vol. 313, no. 4, 517–539 (2013).
Ore O. and Plummer M. D., “Cyclic coloration of plane graphs,” in: Recent Progress in Combinatorics, Academic Press, New York, 1969, 287–293.
Kotzig A., “From the theory of Eulerian polyhedra” (Russian), Mat. Eas. SAV (Math. Slovaca), vol. 13, 20–34 (1963).
Borodin O. V., “Solution of Kotzig’s and Grünbaum’s problems on the separability of a cycle in a planar graph” (Russian), Mat. Zametki, vol. 46, no. 5, 9–12 (1989).
Grünbaum B., “Polytopal graphs. Studies in graph theory. P. II,” Stud. Math., Math. Assoc. Amer., vol. 12, 201–224 (1975).
Jendrol’ S. and Madaras T., “On light subgraphs in plane graphs of minimal degree five,” Discuss. Math. Graph Theory, vol. 16, 207–217 (1996).
Borodin O. V. and Ivanova A. O., “Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5,” Discrete Math., vol. 313, no. 17, 1710–1714 (2013).
Borodin O. V. and Woodall D. R., “Short cycles of low weight in normal plane maps with minimum degree 5,” Discuss. Math. Graph Theory, vol. 8, no. 2, 159–164 (1998).
Borodin O. V., Ivanova A. O., and Jensen T. R., “5-Stars of low weight in normal plane maps with minimum degree 5,” Discuss. Math. Graph Theory, vol. 34, no. 3, 539–546 (2014).
Borodin O. V. and Ivanova A. O., “Light and low 5-stars in normal plane maps with minimum degree 5,” Sib. Math. J., vol. 57, no. 3, 596–602 (2016).
Borodin O. V. and Ivanova A. O., “Light neighborhoods of 5-vertices in 3-polytopes with minimum degree 5,” Sib. Elektron. Math. Rep., vol. 13, 584–591 (2016).
Borodin O. V. and Ivanova A. O., “Low 5-stars in normal plane maps with minimum degree 5,” Discrete Math., vol. 340, no. 2, 18–22 (2017).
Borodin O. V. and Ivanova A. O., “On light neighborhoods of 5-vertices in 3-polytopes with minimum degree 5,” Discrete Math., vol. 340, no. 9, 2234–2242 (2017).
Borodin O. V., Ivanova A. O., and Nikiforov D.V., “Low minor 5-stars in 3-polytopes with minimum degree 5 and no 6-vertices,” Discrete Math., vol. 340, no. 7, 1612–1616 (2017).
Jendrol’ S. and Madaras T., “Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs,” Tatra Mt. Math. Publ., vol. 30, 149–153 (2005).
Ivanova A. O. and Nikiforov D. V., “The structure of neighborhoods of 5-vertices in plane triangulation with minimum degree 5” (Russian), Mat. Zam. YaSU, vol. 20, no. 2, 66–78 (2013).
Ivanova A. O. and Nikiforov D. V., “Combinatorial structure of triangulated 3-polytopes with minimum degree 5,” in: Proceedings of the Scientific Conference of Students, Graduate Students, and Young Researchers, XVII and XVIII Lavrent'ev’s Reading, Yakutsk, Kirov, International Center for Research Project, 2015, 2015, 22–27.
Nikiforov D. V., “The structure of neighborhoods of 5-vertices in normal plane maps with minimum degree 5” (Russian), Mat. Zam. YaSU, vol. 23, no. 1, 56–66 (2016).
Borodin O. V., Ivanova A. O., and Kazak O. N., “Describing neighborhoods of 5-vertices in 3-polytopes with minimum degree 5 and without vertices of degrees from 7 to 11,” Discuss. Math. Graph Theory; DOI:10.7151/dmgt.2024.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text Copyright © 2018 Borodin O.V., Ivanova A.O., and Nikiforov D.V.
The authors were funded by the Russian Science Foundation (Grant 16–11–10054).
Translated from Sibirskiĭ Matematicheskiĭ Zhurnal, Vol. 59, No. 1, pp. 56–64, January–February, 2018; DOI: 10.17377/smzh.2018.59.105
Rights and permissions
About this article
Cite this article
Borodin, O.V., Ivanova, A.O. & Nikiforov, D.V. Describing Neighborhoods of 5-Vertices in a Class of 3-Polytopes with Minimum Degree 5. Sib Math J 59, 43–49 (2018). https://doi.org/10.1134/S0037446618010056
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0037446618010056