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

V. A. Aksenov ; O. V. Borodin ; A. O. Ivanova

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1174-1181.

Résumé

Lebesgue (1940) proved that every plane graph with minimum degree $\delta$ at least $3$ and girth $g$ 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. Borodin and Ivanova (2015) gave seven tight descriptions of $3$-paths when $\delta\ge3$ and $g\ge4$. Furthermore, they 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, they 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, several 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 this paper, we prove ten new tight descriptions of $3$-paths for $\delta=2$ and $g\ge9$ and show that no other tight descriptions exist.

Détail

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

Bibliographie

[1] V.A. Aksenov, Borodin O.V., A.O. Ivanova, “Weight of $3$-paths in sparse plane graphs”, Electronic J. Combin., 22:3 (2015), #P3.28 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p28 | 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) (in Japanese)

[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 (1993), 121–125 | DOI | MR | Zbl

[5] O.V. Borodin, “Precise lower bounds for the number of edges of minor weight in planar maps”, Mathematica Slovaca, 42:2 (1992), 129–142 | MR | Zbl

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

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

[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 one-term tight descriptions of $3$-paths in normal plane maps without $K_4-e$”, Discrete Math., 341:12 (2018), 3425–3433 | DOI | MR

[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] Ph. Franklin, “The four-color problem”, Amer. J. Math., 44:3 (1922), 225–236 | DOI | MR | Zbl

[13] B. Grünbaum, “New views on some old questions of combinatorial geometry”, Int. Teorie Combinatorie (Rome, 1973), v. 1, 1976, 451–468 | MR | Zbl

[14] S. Jendrol', “Paths with restricted degrees of their vertices in planar graphs”, Czechoslovak Math. J., 49(124):3 (1999), 481–490 | 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’, Maceková M., “Describing short paths in plane graphs of girth at least $5$”, Discrete Math., 338:2 (2015), 149–-158 | DOI | MR | Zbl

[17] S. Jendrol’, Maceková M., Montassier M., Soták R., “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] A. Kotzig, “Contribution to the theory of Eulerian polyhedra”, Mat. Čas., 5 (1955), 101–113 (in Slovak) | MR

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

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