All tight descriptions of faces in plane triangulations with minimum degree~4

Borodin, Oleg V. ; Ivanova, Anna O. 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1037-1050

Résumé

It follows from the classical theorem by Lebesgue (1940) on the structure of minor faces in 3-polytopes that every plane triangulation with minimum degree at least 4 has a 3-face for which the set of degrees of its vertices is majorized by one of the following sequences: (4,4,∞), (4,5,19), (4,6,11), (4,7,9), (5,5,9), (5,6,7). In 1999, Jendrol' gave the following description of faces: (4,4,∞), (4,5, 13), (4,6,17), (4,7,8), (5,5,7), (5,6,6). Also, Jendrol' (1999) conjectured that there is a face of one of the types: (4,4,∞), (4,5,10), (4,6,15), (4,7,7), (5,5,7), (5,6,6). In 2002, Lebesgue's description was strengthened by Borodin to (4,4,∞), (4,5,17), (4,6,11), (4,7,8), (5,5,8), (5,6,6). In 2014, we obtained the following tight description, which, in particular, disproves the above mentioned conjecture by Jendrol': (4,4,∞), (4,5,11), (4,6,10), (4,7,7), (5,5,7), (5,6,6). Recently, we obtained another tight description: (4,4,∞), (4,6,10), (4,7,7), (5,5,8), (5,6,7). The purpose of this paper is to give an exhausting list of tight descriptions of faces in plane triangulations with minimum degree at least 4, which turns out to consist of 32 items.

Détail

Keywords: planar graph, face, triangulation, structure properties, 3-polytope, Lebesgue's Theorem

Bibliographie

[1] S.V. Avgustinovich and O.V. Borodin, Edge neighborhoods in normal maps, Diskretn. Anal. Issled. Oper. 2(3) (1989) 9–12, in Russian. Translation in: Mathematics and Its Applications 391 (1997) 17–22, A.D. Korshunov (Eds), Operations Research and Discrete Analysis (Springer Netherlands, 1997) 17–22. https://doi.org/10.1007/978-94-011-5678-3_3

[2] O.V. Borodin, Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Mat. Zametki 46(5) (1989) 9–12, in Russian. Translation in: Math. Notes 46 (1989) 835–837. https://doi.org/10.1007/BF01139613

[3] O.V. Borodin, Minimal weight of face in plane triangulations without 4-vertices, Mat. Zametki 51 (1992) 16–19, in Russian. Translation in: Math. Notes 51 (1992) 11–13. https://doi.org/10.1007/BF01229428

[4] O.V. Borodin, Structural properties of planar maps with minimal degree 5, Math. Nachr. 158 (1992) 109–117. https://doi.org/10.1002/mana.19921580108

[5] O.V. Borodin, Triangulated 3-polytopes without faces of low weight, Discrete Math. 186 (1998) 281–285. https://doi.org/10.1016/S0012-365X(97)00240-9

[6] O.V. Borodin, An improvement of Lebesgues theorem on the structure of minor faces of 3-polytopes, Diskretn. Anal. Issled. Oper. 9(3) (2002) 29–39, in Russian.

[7] O.V. Borodin, Colorings of plane graphs: A survey, Discrete Math. 313 (2013) 517–539. https://doi.org/10.1016/j.disc.2012.11.011

[8] O.V. Borodin and A.O. Ivanova, Describing 3-faces in normal plane maps with minimum degree 4, Discrete Math. 313 (2013) 2841–2847. https://doi.org/10.1016/j.disc.2013.08.028

[9] O.V. Borodin and A.O. Ivanova, Combinatorial structure of faces in triangulations 3-polytopes with minimum degree 4, Sib. Math. J. 55 (2014) 12–18. https://doi.org/10.1134/S0037446614010030

[10] O.V. Borodin and A.O. Ivanova, Low edges in 3-polytopes, Discrete Math. 338 (2015) 2234–2241. https://doi.org/10.1016/j.disc.2015.05.018

[11] O.V. Borodin and A.O. Ivanova, Height of minor faces in triangle-free 3-polytopes, Sib. Math. J. 56 (2015) 783–788. https://doi.org/10.1134/S003744661505002X

[12] O.V. Borodin and A.O. Ivanova, The vertex-face weight of edges in 3-polytopes, Sib. Math. J. 56 (2015) 275–284. https://doi.org/10.1134/S003744661502007X

[13] O.V. Borodin and A.O. Ivanova, New results about the structure of plane graphs: A survey, in: AIP Conf. Proc. 1907 (2017) 030051. https://doi.org/10.1063/1.5012673

[14] O.V. Borodin and A.O. Ivanova, Describing faces in 3-polytopes with no vertices of degree from 5 to 7, Discrete Math. 342 (2019) 3208–3215. https://doi.org/10.1016/j.disc.2019.06.032

[15] O.V. Borodin and A.O. Ivanova, Another tight description of faces in plane triangulations with minimum degree 4, Discrete Math. 345(9) (2022) 112964. https://doi.org/10.1016/j.disc.2022.112964

[16] O.V. Borodin, A.O. Ivanova and A.V. Kostochka, Describing faces in plane triangulations, Discrete Math. 319 (2014) 47–61. https://doi.org/10.1016/j.disc.2013.11.021

[17] O.V. Borodin, A.O. Ivanova and E.I. Vasil'eva, A Steinberg-like approach to describing faces in 3-polytopes, Graphs Combin. 33 (2017) 63–71. https://doi.org/10.1007/s00373-016-1743-6

[18] O.V. Borodin and D.V. Loparev, Height of minor faces in plane normal maps, Diskretn. Anal. Issled. Oper. Ser. 5(4) (1998) 6–17, in Russian. Translation in: Discrete Appl. Math. 135 (2004) 31–39. https://doi.org/10.1016/S0166-218X(02)00292-5

[19] O.V. Borodin and D.R. Woodall, Weight of faces in plane maps, Mat. Zametki 64 (1998) 648–657, in Russian. Translation in: Math. Notes 64 (1998) 562–570. https://doi.org/10.1007/BF02316280

[20] B. Grünbaum, Polytopal graphs, in: Studies in Graph Theory, Part II, D.R. Fulkerson (Ed(s)), MMA Studies in Mathematics 12 (The Mathematical Association of America, Washington, D.C., 1975) 201–224.

[21] M. Horňák and S. Jendrol', Unavoidable set of face types for planar maps, Discuss. Math. Graph Theory 16 (1996) 123–141. https://doi.org/10.7151/dmgt.1028

[22] S. Jendrol', Triangles with restricted degrees of their boundary vertices in plane triangulations, Discrete Math. 196 (1999) 177–196. https://doi.org/10.1016/S0012-365X(98)00172-1

[23] S. Jendrol' and H.-J. Voss, Light subgraphs of graphs embedded in the plane–-A survey, Discrete Math. 313 (2013) 406–421. https://doi.org/10.1016/j.disc.2012.11.007

[24] A. Kotzig, From the theory of Euler's polyhedrons, Mat.-Fyz. Čas. 13 (1963) 20–31, in Russian.

[25] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569–570.

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

[27] B. Mohar, R. Škrekovski and H.-J. Voss, Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9, J. Graph Theory 44 (2003) 261–295. https://doi.org/10.1002/jgt.10144

[28] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: Recent Progress in Combinatorics, W.T. Tutte (Ed(s)), (Academic Press, New York 1969) 287–293.

[29] M.D. Plummer, On the cyclic connectivity of planar graph, in: Graph Theory and Application, (Springer, Berlin 1972) 235–242.

[30] E. Steinitz, Polyeder und Raumeinteilungen, in: Encyklopädie der Mathematischen Wissenschaften, vol. 3 (Geometrie) AB 12 (1922) 1–139, in German.