Geodesic
Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree 5 and Without Vertices of Degrees from 7 to 11
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 615-625.

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

In 1940, Lebesgue proved that every 3-polytope 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). In this paper we prove that every 3-polytope without vertices of degree from 7 to 11 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6), where all parameters are tight.
Keywords: planar graph, structure properties, 3-polytope, neighborhood 
@article{DMGT_2018_38_3_a0,
     author = {Borodin, Oleg V. and Ivanova, Anna O. and Kazak, Olesya N.},
     title = {Describing {Neighborhoods} of {5-Vertices} in {3-Polytopes} with {Minimum} {Degree} 5 and {Without} {Vertices} of {Degrees} from 7 to 11},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {615--625},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a0/}
}
TY  - JOUR
AU  - Borodin, Oleg V.
AU  - Ivanova, Anna O.
AU  - Kazak, Olesya N.
TI  - Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree 5 and Without Vertices of Degrees from 7 to 11
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 615
EP  - 625
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a0/
LA  - en
ID  - DMGT_2018_38_3_a0
ER  - 
%0 Journal Article
%A Borodin, Oleg V.
%A Ivanova, Anna O.
%A Kazak, Olesya N.
%T Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree 5 and Without Vertices of Degrees from 7 to 11
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 615-625
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a0/
%G en
%F DMGT_2018_38_3_a0
Borodin, Oleg V.; Ivanova, Anna O.; Kazak, Olesya N. Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree 5 and Without Vertices of Degrees from 7 to 11. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 615-625. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a0/

[1] V.A. Aksenov, O.V. Borodin and A.O. Ivanova, Weight of 3 -paths in sparse plane graphs, Electron. J. Combin. 22 (2015) #P3.28.

[2] K. Ando, S. Iwasaki and A. Kaneko, Every 3 -connected planar graph has a connected subgraph with small degree sum, Annual Meeting of Mathematical Society of Japan (1993).

[3] O.V. Borodin, Solution of Kotzig’s and Grünbaum’s problems on the separability of a cycle in a planar graph, Mat. Zametki 46 (1989) 9–12, in Russian.

[4] O.V. Borodin, Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps, Diskret. Mat. 3 (1991) 24–27, in Russian.

[5] O.V. Borodin, Joint extension of two Kotzig’s theorems on 3 -polytopes, Combinatorica 13 (1993) 121–125. doi:10.1007/BF01202794

[6] O.V. Borodin, Minimal vertex degree sum of a 3 -path in plane maps, Discuss. Math. Graph Theory 17 (1997) 279–284. doi:10.7151/dmgt.1055

[7] O.V. Borodin, Colorings of plane graphs: a survey, Discrete Math. 313 (2013) 517–539. doi:10.1016/j.disc.2012.11.011

[8] O.V. Borodin and A.O. Ivanova, Describing ( d − 2)- stars at d-vertices, d ≤ 5, in normal plane maps, Discrete Math. 313 (2013) 1700–1709. doi:10.1016/j.disc.2013.04.026

[9] 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. doi:10.1016/j.disc.2013.04.025

[10] 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. doi:10.7151/dmgt.1748

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

[12] O.V. Borodin and A.O. Ivanova, Light and low 5 -stars in normal plane maps with minimum degree 5, Sibirsk. Mat. Zh. 57 (2016) 596–602, in Russian. doi:10.1134/S0037446616030071

[13] 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. doi:10.7151/dmgt.1071

[14] 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. doi:10.1016/j.disc.2009.11.027

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

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

[17] A.O. Ivanova and D.V. Nikiforov, The structure of neighborhoods of 5 -vertices in plane triangulation with minimum degree 5, Mat. Zam. YaSU 20(2) (2013) 66–78, in Russian.

[18] 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 Project (2015) 22–27, in Russian.

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

[20] S. Jendrol’, Paths with restricted degrees of their vertices in planar graphs, Czechoslovak Math. J. 49 (1999) 481–490. doi:10.1023/A:1022411100562

[21] S. Jendrol’ and M. Maceková, Describing short paths in plane graphs of girth at least 5, Discrete Math. 338 (2015) 149–158. doi:10.1016/j.disc.2014.09.014

[22] S. Jendrol’, M. Maceková and R. Soták, Note on 3 -paths in plane graphs of girth 4, Discrete Math. 338 (2015) 1643–1648. doi:10.1016/j.disc.2015.04.011

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

[24] 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.

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

[26] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Eas. SAV (Math. Slovaca) 5 (1955) 101–113.

[27] A. Kotzig, From the theory of Eulerian polyhedra, Mat. Eas. SAV (Math. Slovaca) 13 (1963) 20–34, in Russian.

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

[29] D.V. Nikiforov, The structure of neighborhoods of 5 -vertices in normal plane maps with minimum degree 5, Mat. Zam. YaSU, 23 (2016) 56–66, in Russian.

[30] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: Recent Progress in Combinatorics, W.T. Tutte, (Ed.), (Academic Press, New York, 1969) 287–293.

[31] E. Steinitz, Polyeder und Raumeinteilungen, Enzykl. Math. Wiss. (Geometrie), 3AB 12 (1922) 1–139.

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