Geodesic
All tight descriptions of $3$-paths centered at $2$-vertices in plane graphs with girth at least~$6$
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1334-1344.

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

Lebesgue (1940) proved that every plane graph with minimum degree $\delta$ at least $3$ and girth $g$ (the length of a shortest cycle) at least $5$ has a path on three vertices ($3$-path) of degree $3$ each. A description is tight if no its parameter can be strengthened, and no triplet dropped. Borodin et al. (2013) gave a tight description of $3$-paths in plane graphs with $\delta\ge3$ and $g\ge3$, and another tight description was given by Borodin, Ivanova and Kostochka in 2017. In 2015, we gave seven tight descriptions of $3$-paths when $\delta\ge3$ and $g\ge4$. Furthermore, we proved that this set of tight descriptions is complete, which was a result of a new type in the structural theory of plane graphs. Also, we characterized (2018) all one-term tight descriptions if $\delta\ge3$ and $g\ge3$. The problem of producing all tight descriptions for $g\ge3$ remains widely open even for $\delta\ge3$. Recently, eleven tight descriptions of $3$-paths were obtained for plane graphs with $\delta=2$ and $g\ge4$ by Jendrol', Maceková, Montassier, and Soták, four of which descriptions are for $g\ge9$. In 2018, Aksenov, Borodin and Ivanova proved ten new tight descriptions of $3$-paths for $\delta=2$ and $g\ge9$ and showed that no other tight descriptions exist. In this paper we give a complete list of tight descriptions of $3$-paths centered at a $2$-vertex in the plane graphs with $\delta=2$ and $g\ge6$.
Keywords: plane graph, structure properties, tight description, $3$-path, minimum degree, girth. 
@article{SEMR_2019_16_a71,
     author = {O. V. Borodin and A. O. Ivanova},
     title = {All tight descriptions of $3$-paths centered at $2$-vertices in plane graphs with girth at least~$6$},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1334--1344},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a71/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
TI  - All tight descriptions of $3$-paths centered at $2$-vertices in plane graphs with girth at least~$6$
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 1334
EP  - 1344
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a71/
LA  - en
ID  - SEMR_2019_16_a71
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%T All tight descriptions of $3$-paths centered at $2$-vertices in plane graphs with girth at least~$6$
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 1334-1344
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a71/
%G en
%F SEMR_2019_16_a71
O. V. Borodin; A. O. Ivanova. All tight descriptions of $3$-paths centered at $2$-vertices in plane graphs with girth at least~$6$. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1334-1344. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a71/

[1] V.A. Aksenov, O.V. Borodin, A.O. Ivanova, “All tight descriptions of 3-paths in plane graphs with girth at least 9”, Sib. Elektron. Mat. Izv., 15 (2018), 1174–1181 | MR | Zbl

[2] Ts. Ch-D. Batueva, O.V. Borodin, A.O. Ivanova, “All tight descriptions of 4-paths in 3-polytopes with minimum degree 5”, Graphs and Combinatorics, 33:1 (2017), 53–62 | DOI | MR | Zbl

[3] O.V. Borodin, “On the total coloring of planar graphs”, J. Reine Angew. Math., 394 (1989), 180–185 | MR | Zbl

[4] O.V. Borodin, “Joint extension of two Kotzig's theorems on 3-polytopes”, Combinatorica, 13:1 (1992), 121–125 | DOI | MR

[5] O.V. Borodin, “Structure of neighborhoods of an edge in planar graphs and the simultaneous coloring of vertices, edges and faces”, Math. Notes, 53:5–6 (1993), 483–489 | DOI | MR | Zbl

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

[7] O.V. Borodin, A.O. Ivanova, “Describing 4-paths in 3-polytopes with minimum degree 5”, Siberian Math. J., 57:5 (2016), 764–768 | DOI | MR | Zbl

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

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

[10] O.V. Borodin, A.O. Ivanova, “All one-term tight descriptions of 3-paths in normal plane maps without $K_4-e$”, Discrete Math., 341:12 (2018), 3425–3433 | DOI | MR | Zbl

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

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

[13] D.W. Cranston, D.B. West, “An introduction to the discharging method via graph coloring”, Discrete Math., 340:4 (2017), 766–793 | DOI | MR | Zbl

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

[15] S. Jendrol', “A structural property of convex 3-polytopes”, Geom. Dedicata, 68:1 (1997), 91–99 | 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] S. Jendrol', M. Maceková, M. Montassier, R. Soták, “Optimal unavoidable sets of types of 3-paths for planar graphs of given girth”, Discrete Math., 339:2 (2016), 780–789 | DOI | MR | Zbl

[18] S. Jendrol', M. Maceková, M. Montassier, R. Soták, “3-paths in graphs with bounded average degree”, Discuss. Math. Graph Theory, 36:2 (2016), 339–353 | DOI | MR | Zbl

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

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

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