Abstract: The degree d(x)of a vertex or face xin a graph Gis the number of incident edges. A face f=v1...vd(f)in a graph Gon the plane or other orientable surface is of type (k1, k2, ...), where k1≤k2≤..., if d(vi) ≤kifor each i. By δwe denote the minimum vertex-degree of G. In 1989, Borodin confirmed Kotzig’s conjecture of 1963 that every plane graph with minimum degree δequal to 5 has a (5, 5, 7)-face or a (5, 6, 6)-face, where all parameters are tight. Recently, we proved that every torus triangulation with δ≥5has a face of one of the types (5, 5, 8), (5, 6, 7), or (6, 6, 6), which is tight. It follows from the classical theorem by Lebesgue (1940) that every plane triangulation with δ≥4has a 3-face of types (4, 4, ∞), (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, ∞), (4, 5, 13), (4, 6, 17), (4, 7, 8), (5, 5, 7), (5, 6, 6)” and conjectured that “(4, 4, ∞), (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, ∞), (4, 5, 17), (4, 6, 11), (4, 7, 8), (5, 5, 8), (5, 6, 6)”. In 2014, Borodin and Ivanova 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)”, and recently proved another tight description of faces in plane triangulations with δ≥4: “(4, 4, ∞), (4, 6, 10), (4, 7, 7), (5, 5, 8), (5, 6, 7)”. It follows from Lebesgue’s theorem of 1940 that every plane quadrangulation with δ≥3has a face of one of the types (3, 3, 3, ∞), (3, 3, 4, 11), (3, 3, 5, 7), (3, 4, 4, 5). Recently, Borodin and Ivanova improved this description to “(3, 3, 3, ∞), (3, 3, 4, 9), (3, 3, 5, 6), (3, 4, 4, 5)”, where all parameters except possibly 9are 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, ∞), (3, 3, 4, 10), (3, 3, 5, 7), (3, 3, 6, 6), (3, 4, 4, 6), (4, 4, 4, 4)”, which also holds for each higher surface provided that its quadrangulation is large enough. Recently, Borodin and Ivanova proved that every triangulation with δ≥4of the torus has a face of one of the types (4, 4, ∞), (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 triangulation with δ≥3on the torus has a face of one of the types (3, 6, 24), (3, 8, 16), (3, 12, 12), (4, 4, ∞), (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.
Tight description of faces of triangulations on the torus
Discrete Mathematics. 2023. V.346. N9. 113510 :1-10. DOI: 10.1016/j.disc.2023.113510 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Nov 11, 2022
Accepted:	May 6, 2023
Published online:	May 29, 2023
Published print:	May 31, 2023

Identifiers:

Web of science:	WOS:001013604400001
Scopus:	2-s2.0-85161065728
Elibrary:	63702880
OpenAlex:	W4378894139

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

Altmetrics: