Geodesic
Description of faces in 3-polytopes without vertices of degree from 4 to 9
Matematičeskie zametki SVFU, Tome 23 (2016) no. 3, pp. 46-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In 1940, Lebesgue proved that every normal plane map contains a face for which the set of degrees of its vertices is majorized by one of the following sequences: (3, 6,$\infty$), (3, 7, 41), (3, 8, 23), (3, 9, 17), (3, 10, 14), (3, 11, 13), (4, 4, $\infty$), (4, 5, 19), (4, 6, 11), (4, 7, 9), (5, 5, 9), (5, 6, 7), (3, 3, 3, $\infty$), (3, 3, 4, 11), (3, 3, 5, 7), (3, 4, 4, 5), (3, 3, 3, 3, 5). In this note prove that every 3-polytope without vertices of degree from 4 to 9 contains a face for which the set of degrees of its vertices is majorized by one of the following sequences: (3, 3, $\infty$), (3, 10, 12), (3, 3, 3, $\infty$), (3, 3, 3, 3, 3), which is tight.
Keywords: planar graph, plane map, structure properties, 3-polytope, weight. 
@article{SVFU_2016_23_3_a2,
     author = {A. O. Ivanova},
     title = {Description of faces in 3-polytopes without vertices of degree from 4 to 9},
     journal = {Matemati\v{c}eskie zametki SVFU},
     pages = {46--54},
     year = {2016},
     volume = {23},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVFU_2016_23_3_a2/}
}
TY  - JOUR
AU  - A. O. Ivanova
TI  - Description of faces in 3-polytopes without vertices of degree from 4 to 9
JO  - Matematičeskie zametki SVFU
PY  - 2016
SP  - 46
EP  - 54
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/SVFU_2016_23_3_a2/
LA  - ru
ID  - SVFU_2016_23_3_a2
ER  - 
%0 Journal Article
%A A. O. Ivanova
%T Description of faces in 3-polytopes without vertices of degree from 4 to 9
%J Matematičeskie zametki SVFU
%D 2016
%P 46-54
%V 23
%N 3
%U http://geodesic.mathdoc.fr/item/SVFU_2016_23_3_a2/
%G ru
%F SVFU_2016_23_3_a2
A. O. Ivanova. Description of faces in 3-polytopes without vertices of degree from 4 to 9. Matematičeskie zametki SVFU, Tome 23 (2016) no. 3, pp. 46-54. http://geodesic.mathdoc.fr/item/SVFU_2016_23_3_a2/

[1] Lebesgue H., “Quelques conséquences simples de la formule d'Euler”, J. Math. Pures Appl., 19 (1940), 27–43 | MR

[2] Borodin O. V., “Colorings of plane graphs: a survey”, Discrete Math ., 313:4 (2013), 517–539 | DOI | MR | Zbl

[3] Ore O., Plummer M. D., “Cyclic coloration of plane graphs”, Recent progress in combinatorics, ed. W. T. Tutte, Acad. Press, New York, 1969, 287–293 | MR

[4] Plummer M. D., Toft B., “Cyclic coloration of 3-polytopes”, J. Graph Theory, 11 (1987), 507–515 | DOI | MR | Zbl

[5] Kotzig A., “From the theory of Eulerian polyhedra (Russian)”, Mat. Cas, 13 (1963), 20–31 | MR

[6] Borodin O. V., “Solution of Kotzig’s and Grünbaum’s problems on the separability of a cycle in a planar graph”, Mat. Zametki, 46:5 (1989), 9–12 | MR

[7] Grünbaum B., “Polytopal graphs”, Studies in graph theory, MAA Stud. Math., 12, ed. D. R. Fulkerson, 1975, 201–224 | MR | Zbl

[8] Plummer M. D., “On the cyclic connectivity of planar graph”, Graph theory and application, Springer-Verl., Berlin, 1972, 235–242 | DOI | MR

[9] Steinitz E., “Polyeder und Raumeinteilungen”, Geometrie, v. 3AB, Enzykl. Math. Wiss., 12, 1922, 1–139

[10] Kotzig A., “Extremal polyhedral graphs”, Ann. New York Acad. Sci, 319. (1979), 569–570

[11] Borodin O. V., “Minimal weight of face in plane triangulations without 4-vertices”, Mat. Zametki, 51:1 (1992), 16–19 | MR | Zbl

[12] Borodin O. V., “Triangulated 3-polytopes with restricted minimal weight of faces”, Discrete Math, 186. (1998), 281–285 | DOI | MR | Zbl

[13] Horňá M., Jendrol' S., “Unavoidable sets of face types for planar maps”, Discuss. Math. Graph Theory, 16:2 (1996), 123–142 | DOI | MR

[14] Borodin O. V. and Woodall D. R., “The weight of faces in plane maps”, Mat. Zametki, 6:5 (1998), 648–657 | DOI

[15] Avgustinovich S. V. and Borodin O. V., “Neighborhoods of edges in normal maps”, Diskretn. Anal. Issled. Oper., 2:3 (1995), 3–9 | MR

[16] Jendrol' S., Voss H.-J., “Light subgraphs of graphs embedded in the plane - a survey”, Discrete Math, 313:4 (2013), 406–421 | DOI | MR | Zbl

[17] Borodin O. V., “Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps”, Diskret. Mat., 3:4 (1991), 24–27 | MR | Zbl

[18] Borodin O. V. and Loparev D. V., “The height of small faces in planar normal maps”, Diskretn. Anal. Issled. Oper. Ser., 5:4 (1998), 6–17 | MR | Zbl

[19] Ferencová B., Madaras T., “On the structure of polyhedral graphs with prescribed edge and dual edge weight”, Acta Univ. M. Belii Math, 12 (2005), 13–18 | MR | Zbl

[20] Ferencová B., Madaras T., “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 | MR | Zbl

[21] Jendrol' S., “Triangles with restricted degrees of their boundary vertices in plane triangulations”, Discrete Math, 196. (1999), 177–196 | DOI | MR | Zbl

[22] Madaras T., Soták R., “The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five”, Tatra Mt. Math. Publ, 18 (1999), 35–56 | MR | Zbl

[23] Madaras T., Skrekovski R., Voss H.-J., “The 7-cycle C7 is light in the family of planar graphs with minimum degree 5”, Discrete Math, 307 (2007), 1430–1435 | DOI | MR | Zbl

[24] Mohar B., Skrekovski R., Voss H.-J., “Light subraphs in planar graphs of minimum degree 4 and edge-degree 9”, J. Graph Theory, 44 (2003), 261–295 | DOI | MR | Zbl

[25] Madaras T., Skrekovski R., “Heavy paths, light stars, and big melons”, Discrete Math, 286 (2004), 115–131 | DOI | MR | Zbl

[26] Borodin O. V., “An improvement of Lebesgue’s theorem on the structure of minor faces of 3-polytopes”, Diskretn. Anal. Issled. Oper., 9:3 (2002), 29–39 | Zbl

[27] Borodin O. V., Ivanova A. O., “Describing 3-faces in normal plane maps with minimum degree 4”, Discrete Math, 313:23 (2013), 2841–2847 | DOI | MR | Zbl

[28] Borodin O. V., Woodall D. R., “Cyclic degrees of 3-polytopes”, Graphs Comb., 15 (1999), 267–277 | DOI | MR | Zbl

[29] Kotzig A., “Contribution to the theory of Eulerian polyhedra”, Mat.-Fyz. Cas., 5 (1955), 101–113 | MR

[30] Wernicke P., “Uber den kartographischen Vierfarbensatz”, Math. Ann, 58 (1904), 413–426 | DOI | MR | Zbl