All tight descriptions of $3$-paths in plane graphs with girth at least~$8$

O. V. Borodin ; A. O. Ivanova

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 496-501.

Résumé

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 nine new tight descriptions of $3$-paths for $\delta=2$ and $g\ge9$ and showed that no other tight descriptions exist. The purpose of this note is to give a complete list of tight descriptions of $3$-paths in the plane graphs with $\delta=2$ and $g\ge8$.

Détail

Keywords: Plane graph, structure properties, tight description, $3$-path, minimum degree, height, weight, girth.

Bibliographie

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

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

[3] 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[18] B. Grünbaum, “New views on some old questions of combinatorial geometry”, Colloq. int. Teorie comb., Roma 1973, v. 1, 1976, 451–468 | Zbl

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

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

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

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

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

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

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

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

[27] A. Kotzig, “Contribution to the theory of Eulerian polyhedra”, Mat. Čas., 5 (1955), 101–103 (Slovak) | MR

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

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