Tight description of faces in torus triangulations with minimum degree~5

O. V. Borodin ; A. O. Ivanova

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 2, pp. 1475-1481.

Résumé

The degree $d$ of a vertex or face in a graph $G$ is the number of incident edges. A face $f=v_1\ldots v_{d}$ in a plane or torus graph $G$ is of type $(k_1,k_2,\ldots, k_d)$ if $d(v_i)\le k_i$ for each $i$. By $\delta$ we denote the minimum vertex-degree of $G$. In 1989, Borodin confirmed Kotzig's conjecture of 1963 that every plane graph with minimum degree $\delta$ equal to 5 has a $(5,5,7)$-face or a $(5,6,6)$-face, where all parameters are tight. It follows from the classical theorem of Lebesgue (1940) that every plane quadrangulation with $\delta\ge3$ has a face of one of the types $(3,3,3,\infty)$, $(3,3,4,11)$, $(3,3,5,7)$, $(3,4,4,5)$. Recently, we improved this description to the following one: "$(3,3,3,\infty)$, $(3,3,4,9)$, $(3,3,5,6)$, $(3,4,4,5)$", where all parameters except possibly $9$ are best possible and 9 cannot go down below 8. In 1995, Avgustinovich and Borodin proved that every torus quadrangulation with $\delta\ge3$ has a face of one of the following types: $(3,3,3,\infty)$, $(3, 3, 4, 10)$, $(3, 3, 5, 7)$, $(3, 3, 6, 6)$, $(3, 4, 4, 6)$, $(4, 4, 4, 4)$, where all parameters are best possible. The purpose of our note is to prove that every torus triangulation with $\delta\ge5$ has a face of one of the types $(5,5,8)$, $(5,6,7)$, or $(6,6,6)$, where all parameters are best possible.

Détail

Keywords: plane graph, structure properties, 3-faces.
Mots-clés : torus, triangulation, quadrangulation

Bibliographie

[1] S.V. Avgustinovich, O.V. Borodin, “Edge neighborhoods in normal maps”, Operations research and discrete analysis, Mathematics and its applications, 391, ed. Korshunov A.D., 1997, 17–22 | MR | Zbl

[2] O.V. Borodin, “Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs”, Math. Notes, 46:5 (1989), 835–837 | DOI | MR | Zbl

[3] O.V. Borodin, “Triangulated 3-polytopes without faces of low weight”, Discrete Math., 186:1–3 (1998), 281–285 | DOI | MR | Zbl

[4] O.V. Borodin, “Sharpening Lebesgue's theorem on the structure of lowest faces of convex polytopes”, Diskretn. Anal. Issled. Oper., Ser. 1, 9:3 (2002), 29–39 | MR | Zbl

[5] O.V. Borodin, “Colorings of plane graphs: a survey”, Discrete Math., 313:4 (2013), 517–539 | DOI | MR | Zbl

[6] O.V. Borodin, A.O. Ivanova, “Describing 3-faces in normal plane maps with minimum degree 4”, Discrete Math., 313:23 (2013), 2841–2847 | DOI | MR | Zbl

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

[8] O.V. Borodin, A.O. Ivanova, “An improvement of Lebesgue's description of edges in $3$-polytopes and faces in plane quadrangulations”, Discrete Math., 342:6 (2019), 1820–1827 | DOI | MR | Zbl

[9] O.V. Borodin, A.O. Ivanova, A.V. Kostochka, “Describing faces in plane triangulations”, Discrete Math., 319 (2014), 47–61 | DOI | MR | Zbl

[10] B. Grünbaum, “Polytopal graphs”, Studies in Graph Theory, MAA Studies in Mathematics, 12, ed. D. R. Fulkerson, 1975, 201–224 | MR | Zbl

[11] M. Horňák, S. Jendrol', “Unavoidable sets of face types for planar maps”, Discuss. Math., Graph Theory, 16:2 (1996), 123–141 | DOI | MR | Zbl

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

[13] A. Kotzig, “From the theory of Euler's polyhedrons”, Mat.-Fyz. Čas., 13 (1963), 20–30 | MR | Zbl

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

[15] O. Ore, M.D. Plummer, “Cyclic coloration of plane graphs”, Recent Progr. Comb., Proc. 3rd Waterloo Conf. (1968), 1969, 287–293 | MR | Zbl

[16] M.D. Plummer, “On the cyclic connectivity of planar graph”, Graph Theory Appl., Lect. Notes Math., 303, 1972, 235–242 | DOI | MR | Zbl