Geodesic
Tight description of 4-paths in 3-polytopes with minimum degree 5
Matematičeskie zametki SVFU, Tome 23 (2016) no. 1, pp. 46-55 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Back in 1922, Franklin proved that every 3-polytope P5 with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol' and Madaras (1996) ensured a 4-path with the vertex degree-sum at most 23. The purpose of this note is to prove that every P5 has a (5, 6, 6, 6)-path or (5, 5, 5, 7)-path, where all parameters are tight.
Keywords: planar graph, plane map, structural properties, 3-polytope, 4-path. 
@article{SVFU_2016_23_1_a4,
     author = {A. O. Ivanova},
     title = {Tight description of 4-paths in 3-polytopes with minimum degree 5},
     journal = {Matemati\v{c}eskie zametki SVFU},
     pages = {46--55},
     year = {2016},
     volume = {23},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVFU_2016_23_1_a4/}
}
TY  - JOUR
AU  - A. O. Ivanova
TI  - Tight description of 4-paths in 3-polytopes with minimum degree 5
JO  - Matematičeskie zametki SVFU
PY  - 2016
SP  - 46
EP  - 55
VL  - 23
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SVFU_2016_23_1_a4/
LA  - ru
ID  - SVFU_2016_23_1_a4
ER  - 
%0 Journal Article
%A A. O. Ivanova
%T Tight description of 4-paths in 3-polytopes with minimum degree 5
%J Matematičeskie zametki SVFU
%D 2016
%P 46-55
%V 23
%N 1
%U http://geodesic.mathdoc.fr/item/SVFU_2016_23_1_a4/
%G ru
%F SVFU_2016_23_1_a4
A. O. Ivanova. Tight description of 4-paths in 3-polytopes with minimum degree 5. Matematičeskie zametki SVFU, Tome 23 (2016) no. 1, pp. 46-55. http://geodesic.mathdoc.fr/item/SVFU_2016_23_1_a4/

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

[2] Franklin P., “The four color problem”, Amer. J. Math., 44 (1922), 225–236 | DOI | MR | Zbl

[3] Aksenov V. A., Borodin O. V., Ivanova A. O., “Weight of 3-paths in sparse plane graphs”, Electron. J. Comb, 22:3 (2015), 3.28 | MR | Zbl

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

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

[6] Borodin O. V., “Structural properties of plane maps with minimum degree 5”, Math. Nachr., 18 (1992), 109–117 | MR

[7] Borodin O. V., “Structural theorem on plane graphs with application to the entire coloring”, J. Graph Theory, 23:3 (1996), 233–239 | 3.0.CO;2-T class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[8] Borodin O. V., “Minimal vertex degree sum of a 3-path in plane maps”, Discuss. Math. Graph Theory, 17:2 (1997), 279–284 | DOI | MR | Zbl

[9] Borodin O. V., Ivanova A. O., “Describing (d-2)-stars at d-vertices, d$\le$5, in normal plane maps”, Discrete Math., 313:17 (2013), 1700–1709 | DOI | MR | Zbl

[10] Borodin O. V., Ivanova A. O., “Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5”, Discrete Math, 313:17 (2013), 1710–1714 | DOI | MR | Zbl

[11] 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

[12] Borodin O. V. and Ivanova A. O., “Each 3-polytope with minimum degree 5 has a 7-cycle with maximum degree at most 15”, Sib. Math. J., 56:4 (2015), 612–623 | DOI | MR | Zbl

[13] Borodin O. V., Ivanova A. O., “Describing tight descriptions of 3-paths in triangle-free normal plane maps”, Discrete Math, 338:11. (2015), 1947–1952 | DOI | MR | Zbl

[14] Borodin O. V., Ivanova A. O., Jensen T. R., “5-Stars of low weight in normal plane maps with minimum degree 5”, Discuss. Math. Graph Theory, 34:3 (2014), 539–546 | DOI | MR | Zbl

[15] Borodin O. V., Ivanova A. O., Jensen T. R., Kostochka A. V., Yancey M. P., “Describing 3-paths in normal plane maps”, Discrete Math, 313:23 (2013), 2702–2711 | DOI | MR | Zbl

[16] Borodin O. V., Ivanova A. O., Kostochka A. V., “Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11”, Discrete Math, 315–316 (2014), 128–134 | DOI | MR | Zbl

[17] Borodin O. V., Ivanova A. O., Kostochka A. V., “Describing faces in plane triangulations”, Discrete Math, 319. (2014), 47–61 | DOI | MR | Zbl

[18] Borodin O. V., Ivanova A. O., Kostochka A. V., “Tight descriptions of 3-paths in normal plane maps”, J. Graph Theory, 85 (2016), 115–132 (to appear) | DOI | MR

[19] Borodin O. V., Woodall D. R., “Short cycles of low weight in normal plane maps with minimum degree 5”, Discuss. Math. Graph Theory, 18:2 (1998), 159–164 | DOI | MR | Zbl

[20] Ferencová B., Madaras T., “Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight”, Discrete Math., 310:12 (2010), 1661–1675 | DOI | MR | Zbl

[21] Hudak P., Madaras T., “On doubly light triangles in plane graphs”, Discrete Math, 313:19 (2013), 1978–1988 | DOI | MR | Zbl

[22] Jendrol' S., “Paths with restricted degrees of their vertices in planar graphs”, Czechoslovak Math. J., 49 (1999), 481–490 | DOI | MR | Zbl

[23] Jendrol' S., “A structural property of convex 3-polytopes”, Geom. Dedicata, 68 (1997), 91–99 | DOI | MR | Zbl

[24] Jendrol' S., Madaras T., “On light subgraphs in plane graphs with minimum degree five”, Discuss. Math. Graph Theory, 16:2 (1996), 207–217 | DOI | MR

[25] Jendrol' S., Madaras T., Soták R., Tuza Z., “On light cycles in plane triangulations”, Discrete Math., 197-198. (1999), 453–467 | DOI | MR | Zbl

[26] 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

[27] Jendrol' S., Maceková M., “Describing short paths in plane graphs of girth at least 5”, Discrete Math, 338:2 (2015), 149–158 | DOI | MR | Zbl

[28] Jendrol' S., Maceková M., Soták R., “Note on 3-paths in plane graphs of girth 4”, Discrete Math, 338:9 (2015), 1643–1648 | DOI | MR | Zbl

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

[30] 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

[31] Madaras T., “Note on the weight of paths in plane triangulations of minimum degree 4 and 5”, Discuss. Math. Graph Theory, 20:2 (2000), 173–180 | DOI | MR | Zbl

[32] Madaras T., “On the structure of plane graphs of minimum face size 5”, Discuss. Math. Graph Theory, 24:3 (2004), 403–411 | DOI | MR | Zbl

[33] Madaras T., “Two variations of Franklin's theorem”, Tatra Mt. Math. Publ, 36 (2007), 61–70 | MR | Zbl

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

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

[36] Borodin O. V., Ivanova A. O., “An analogue of Franklin's Theorem”, Discrete Math, 339:10 (2016), 2553–2556 | DOI | MR | Zbl

[37] BorodinO. V., Ivanova A. O., “Describing 4-paths in 3-polytopes with minimum degree 5”, Sib. Math. J., 57:5 (2016), 981–987 | MR | Zbl