Geodesic
An extension of Franklin's Theorem
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 1516-1521.

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

Back in 1922, Franklin proved that every $3$-polytope 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. It is well-known that each $3$-polytope has a vertex of degree at most $5$, called minor vertex. 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$. A $3$-path is minor $3$-path if its central vertex is minor. The purpose of this note is to extend Franklin' Theorem to the $3$-polytopes with minimum degree at least $4$ by proving that there exist precisely the following ten tight descriptions of minor $3$-paths:$\{(6,5,6),(4,4,9),(6,4,8),(7,4,7)\}$, $\{(6,5,6),(4,4,9),(7,4,8)\}$, $\{(6,5,6),(6,4,9),(7,4,7)\}$, $\{(6,5,6),(7,4,9)\}$, $\{(6,5,8),(4,4,9),(7,4,7)\}$,$\{(6,5,9),(7,4,7)\}$, $\{(7,5,7),(4,4,9),(6,4,8)\}$, $\{(7,5,7),(6,4,9)\}$,$\{(7,5,8),(4,4,9)\}$, and $\{(7,5,9)\}$.
Keywords: planar graph, plane map, $3$-polytope, structure properties, tight description, path, weight. 
@article{SEMR_2020_17_a75,
     author = {O. V. Borodin and A. O. Ivanova},
     title = {An extension of {Franklin's} {Theorem}},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1516--1521},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a75/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
TI  - An extension of Franklin's Theorem
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 1516
EP  - 1521
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a75/
LA  - en
ID  - SEMR_2020_17_a75
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%T An extension of Franklin's Theorem
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 1516-1521
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a75/
%G en
%F SEMR_2020_17_a75
O. V. Borodin; A. O. Ivanova. An extension of Franklin's Theorem. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 1516-1521. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a75/

[1] V.A. Aksenov, O.V. Borodin, A.O. Ivanova, “Weight of $3$-paths in sparse plane graphs”, Electro. 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 the separation of a cycle in planar graphs”, Mat. Zametki, 46:5 (1989), 9–12 | MR | Zbl

[4] O.V. Borodin, “Structural properties of plane 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. Elektron. Mat. Izv., 16 (2019), 1334–1344 | DOI | MR | Zbl

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

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

[12] P. Franklin, “The four color problem”, American J., 44 (1922), 225–236 | MR | Zbl

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

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

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

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

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

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

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

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