Geodesic
Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 535-548.

Voir la notice de l'article provenant de la source Library of Science

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. (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) Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P5. In 2018, Borodin, Ivanova, Kazak proved that every forbidding vertices of degree from 7 to 11 results in a tight description (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6). Recently, Borodin, Ivanova, and Kazak proved every 3-polytope in P5 with no vertices of degrees 6, 7, and 8 has a 5-vertex whose neighborhood is majorized by one of the sequences (5, 5, 5, 5, ∞) and (5, 5, 10, 5, 12), which is tight and improves a corresponding description (5, 5, 5, 5, ∞), (5, 5, 9, 5, 17), (5, 5, 10, 5, 14), (5, 5, 11, 5, 13) that follows from the Lebesgue Theorem. The purpose of this paper is to prove that every 3-polytope with minimum degree 5 and no vertices of degree 6 or 7 has a 5-vertex whose neighborhood is majorized by one of the ordered sequences (5, 5, 5, 5, ∞), (5, 5, 8, 5, 14), or (5, 5, 10, 5, 12).
Keywords: planar graph, structural properties, 3-polytope, 5-star, neighborhood 
@article{DMGT_2022_42_2_a11,
     author = {Batueva, Ts.Ch-D. and Borodin, O.V. and Ivanova, A.O. and Nikiforov, D.V.},
     title = {Describing {Minor} {5-Stars} in {3-Polytopes} with {Minimum} {Degree} 5 and {No} {Vertices} of {Degree} 6 or 7},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {535--548},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a11/}
}
TY  - JOUR
AU  - Batueva, Ts.Ch-D.
AU  - Borodin, O.V.
AU  - Ivanova, A.O.
AU  - Nikiforov, D.V.
TI  - Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 535
EP  - 548
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a11/
LA  - en
ID  - DMGT_2022_42_2_a11
ER  - 
%0 Journal Article
%A Batueva, Ts.Ch-D.
%A Borodin, O.V.
%A Ivanova, A.O.
%A Nikiforov, D.V.
%T Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 535-548
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a11/
%G en
%F DMGT_2022_42_2_a11
Batueva, Ts.Ch-D.; Borodin, O.V.; Ivanova, A.O.; Nikiforov, D.V. Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 535-548. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a11/

[1] O.V. Borodin and A.O. Ivanova, Describing 4 -stars at 5 -vertices in normal plane maps with minimum degree 5, Discrete Math. 313 (2013) 1710–1714. https://doi.org/10.1016/j.disc.2013.04.025

[2] O.V. Borodin and A.O. Ivanova, An analogue of Franklin’s Theorem, Discrete Math. 339 (2016) 2553–2556. https://doi.org/10.1016/j.disc.2016.04.019

[3] O.V. Borodin and A.O. Ivanova, Light and low 5 -stars in normal plane maps with minimum degree 5, Sib. Math. J. 57 (2016) 470–475. https://doi.org/10.1134/S0037446616030071

[4] O.V. Borodin and A.O. Ivanova, New results about the structure of plane graphs: a survey, AIP Conference Proceedings 1907 (2017) 030051. https://doi.org/10.1063/1.5012673

[5] O.V. Borodin and A.O. Ivanova, Low 5 -stars in normal plane maps with minimum degree 5, Discrete Math. 340 (2017) 18–22. https://doi.org/10.1016/j.disc.2016.07.013

[6] O.V. Borodin and A.O. Ivanova, On light neighborhoods of 5 -vertices in 3 -polytopes with minimum degree 5, Discrete Math. 340 (2017) 2234–2242. https://doi.org/10.1016/j.disc.2017.04.012

[7] O.V. Borodin, A.O. Ivanova and T.R. Jensen, 5 -stars of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory 34 (2014) 539–546. https://doi.org/10.7151/dmgt.1748

[8] O.V. Borodin, A.O. Ivanova and O.N. Kazak, 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 38 (2018) 615–625. https://doi.org/10.7151/dmgt.2024

[9] O.V. Borodin, A.O. Ivanova, O.N. Kazak and 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 Math. 341 (2018) 825–829. https://doi.org/10.1016/j.disc.2017.11.021

[10] O.V. Borodin, A.O. Ivanova and O.N. Kazak, Describing the neighborhood of 5 -stars in 3 -polytopes with minimum degree 5 and no vertices of degree from 6 to 8, Discrete Math. 342 (2019) 2439–2444. https://doi.org/10.1016/j.disc.2019.05.010

[11] O.V. Borodin and A.O. Ivanova, Light minor 5 -stars in 3 -polytopes with minimum degree 5, Sib. Math. J. 60 (2019) 272–278. https://doi.org/10.1134/S0037446619020071

[12] O.V. Borodin, A.O. Ivanova and D.V. Nikiforov, Low and light 5 -stars in 3 -polytopes with minimum degree 5 and restrictions on the degrees of major vertices, Sib. Math. J. 58 (2017) 600–605. https://doi.org/10.1134/S003744661704005X

[13] O.V. Borodin, A.O. Ivanova and D.V. Nikiforov, Low minor 5 -stars in 3 -polytopes with minimum degree 5 and no 6 -vertices, Discrete Math. 340 (2017) 1612–1616. https://doi.org/10.1016/j.disc.2017.03.002

[14] O.V. Borodin and D.R. Woodall, Short cycles of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory 18 (1998) 159–164. https://doi.org/10.7151/dmgt.1071

[15] B. Ferencová and T. Madaras, Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight, Discrete Math. 310 (2010) 1661–1675. https://doi.org/10.1016/j.disc.2009.11.027

[16] Ph. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225–236. https://doi.org/10.2307/2370527

[17] J. Harant and S. Jendrol’, On the existence of specific stars in planar graphs, Graphs Combin. 23 (2007) 529–543. https://doi.org/10.1007/s00373-007-0747-7

[18] A.O. Ivanova and D.V. Nikiforov, The structure of neighborhoods of 5 -vertices in plane triangulation with minimum degree 5, Math. Notes of Yakutsk State University 20 (2013) 66–78, in Russian.

[19] A.O. Ivanova and D.V. Nikiforov, 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 Projects, 2015) 22–27, in Russian.

[20] S. Jendrol’, A structural property of convex 3 -polytopes, Geom. Dedicata 68 (1997) 91–99. https://doi.org/10.1023/A:1004993723280

[21] S. Jendrol’ and T. Madaras, On light subgraphs in plane graphs of minimum degree five, Discuss, Math. Graph Theory 16 (1996) 207–217. https://doi.org/10.7151/dmgt.1035

[22] S. Jendrol’ and T. Madaras, Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs, Tatra Mt. Math. Publ. 30 (2005) 149–153.

[23] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane—A survey, Discrete Math. 313 (2013) 406–421. https://doi.org/10.1016/j.disc.2012.11.007

[24] H. Lebesgue, Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19 (1940) 27–43.

[25] Y. Li, M. Rao and T. Wang, Minor stars in plane graphs with minimum degree five, Discrete Appl. Math. 257 (2019) 233–242. https://doi.org/10.1016/j.dam.2018.10.019

[26] D.V. Nikiforov, The structure of neighborhoods of normal plane maps with minimum degree 5, Math. Notes of North-Eastern Federal University 23 (2016) 56–66, in Russian.

[27] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413–426. https://doi.org/10.1007/BF01444968