Geodesic
All tight descriptions of major $3$-paths in $3$-polytopes without $3$-vertices
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 456-463.

Voir la notice de l'article provenant de la source Math-Net.Ru

A $3$-path $uvw$ is an $(i,j,k)$-path if $d(u)\le i$, $d(v)\le j$, and $d(w)\le k$, where $d(x)$ is the degree of a vertex $x$. It is well-known that each $3$-polytope has a vertex of degree at most $5$, called minor. A description of $3$-paths in a $3$-polytope is minor or major if the central item of each its triplet is at most 5 or at least $6$, respectively. Back in 1922, Franklin proved that each $3$-polytope with minimum degree 5 has a $(6,5,6)$-path, which description is tight. Recently, Borodin and Ivanova extended Franklin's theorem by producing all the ten tight minor descriptions of $3$-paths in the class $\mathbf{P_4}$ of $3$-polytopes with minimum degree at least $4$. In 2016, Borodin and Ivanova proved that each polytope with minimum degree $5$ has a $(5,6,6)$-path, and there exists no tight description of $3$-paths in this class of $3$-polytopes other than $\{(6,5,6)\}$ and $\{(5,6,6)\}$. The purpose of this paper is to prove that there exist precisely the following four major tight descriptions of $3$-paths in $\mathbf{ P_4}$: $\{(4,9,4),(4,7,5),(5,6,6)\}$, $\{(4,9,4),(5,7,6)\}$, $\{(4,9,5),(5,6,6)\}$, and $\{(5,9,6)\}$.
Keywords: plane graph, $3$-polytope, structural properties, $3$-path, tight description. 
@article{SEMR_2021_18_1_a15,
     author = {Ts. Ch.-D. Batueva and O. V. Borodin and A. O. Ivanova and D. V. Nikiforov},
     title = {All tight descriptions of major $3$-paths in $3$-polytopes without $3$-vertices},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {456--463},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a15/}
}
TY  - JOUR
AU  - Ts. Ch.-D. Batueva
AU  - O. V. Borodin
AU  - A. O. Ivanova
AU  - D. V. Nikiforov
TI  - All tight descriptions of major $3$-paths in $3$-polytopes without $3$-vertices
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2021
SP  - 456
EP  - 463
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a15/
LA  - en
ID  - SEMR_2021_18_1_a15
ER  - 
%0 Journal Article
%A Ts. Ch.-D. Batueva
%A O. V. Borodin
%A A. O. Ivanova
%A D. V. Nikiforov
%T All tight descriptions of major $3$-paths in $3$-polytopes without $3$-vertices
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2021
%P 456-463
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a15/
%G en
%F SEMR_2021_18_1_a15
Ts. Ch.-D. Batueva; O. V. Borodin; A. O. Ivanova; D. V. Nikiforov. All tight descriptions of major $3$-paths in $3$-polytopes without $3$-vertices. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 456-463. http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a15/

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

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

[3] O.V. Borodin, “Solution of Kotzig-Grünbaum problems on separation of a cycle in planar graphs”, Mat. Zametki, 46:5 (1989), 9–12 | MR | Zbl

[4] O.V. Borodin, “Structural properties of planar maps with the minimal degree $5$”, Math. Nachr., 158 (1992), 109–117 | DOI | MR | Zbl

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

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

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

[8] O.V. Borodin, A.O. Ivanova, “New results about the structure of plane graphs: a survey”, AIP Conference Proceedings, 1907 (2017), 030051 | DOI | MR

[9] O.V. Borodin, A.O. Ivanova, “All tight descriptions of $3$-paths centered at $2$-vertices in plane graphs with girth at least $6$”, Sib. Électron. Mat. Izv., 16 (2019), 1334–1344 | DOI | MR | Zbl

[10] O.V. Borodin, A.O. Ivanova, “An extension of Franklin's theorem”, Sib. Électron. Math. Izv., 17 (2020), 1516–1521 | DOI | MR | Zbl

[11] O.V. Borodin, A.O. Ivanova, “A tight description of $3$-polytopes by major $3$-paths”, Siberian Math. J. (to appear)

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

[13] O.V. Borodin, A.O. Ivanova, A.V. Kostochka, “Tight descriptions of $3$-paths in normal plane maps”, J. Graph Theory, 85:1 (2017), 115–132 | DOI | MR | Zbl

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

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

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

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

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

[19] T. Madaras, “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

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

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

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