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