Abstract: The degree d(x) of a vertex or face x in a graph G is the number of incident edges. A face f = v1 . . . vd(f) in a graph G on the plane or other orientable surface is of type (k1, k2, . . .) if d(vi) ki for each i. By we denote the minimum vertex-degree of G. It follows from the classical theorem by Lebesgue (1940) that every plane triangulation with 4 has a 3-face of types (4, 4,1), (4, 5, 19), (4, 6, 11), (4, 7, 9), (5, 5, 9), or (5, 6, 7). In 1999, Jendrol’ gave a similar description: “(4, 4,1), (4, 5, 13), (4, 6, 17), (4, 7, 8), (5, 5, 7), (5, 6, 6)” and conjectured that “(4, 4,1), (4, 5, 10), (4, 6, 15), (4, 7, 7), (5, 5, 7), (5, 6, 6)” holds. In 2002, Lebesgue’s description was strengthened by Borodin to “(4, 4,1), (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,1), (4, 5, 11), (4, 6, 10), (4, 7, 7), (5, 5, 7), (5, 6, 6)”, and recently proved another tight description of faces in plane triangulations with 4: “(4, 4,1), (4, 6, 10), (4, 7, 7), (5, 5, 8), (5, 6, 7)”. It follows from Lebesgue’ theorem of 1940 that every plane 3-connected quadrangulation has a face of one of the types (3, 3, 3,1), (3, 3, 4, 11), (3, 3, 5, 7), (3, 4, 4, 5). Recently, we improved this description to “(3, 3, 3,1), (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 the following tight description of the faces of torus quadrangulations with 3: “(3, 3, 3,1), (3, 3, 4, 10), (3, 3, 5, 7), (3, 3, 6, 6), (3, 4, 4, 6), (4, 4, 4, 4)”. Recently, we proved that every triangulation with 4 of the torus has a face of one of the types (4, 4,1), (4, 6, 12), (4, 8, 8), (5, 5, 8), (5, 6, 7), or (6, 6, 6), which description is tight. The purpose of this paper is to prove that every 3-connected graph with 4 embedded on the torus has a face of one of the types (4, 4, 4, 4), (4, 4,1), (4, 5, 16), (4, 6, 12), (4, 8, 8), (5, 5, 8), (5, 6, 7), or (6, 6, 6), where all parameters are best possible.

Cite: Borodin O.V. , Ivanova A.O.
All tight descriptions of faces in plane triangulations with minimum degree 4
Discussiones Mathematicae - Graph Theory. 2024. V.44. N3. P.1037-1050. DOI: 10.7151/dmgt.2488 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Nov 28, 2022
Accepted:	Jan 26, 2023
Published online:	Feb 23, 2023
Published print:	May 2, 2024

Identifiers:

Web of science:	WOS:001145783800001
Scopus:	2-s2.0-85193227578
Elibrary:	60805603
OpenAlex:	W4321795979

Citing: Пока нет цитирований

Altmetrics: