Аннотация:
The degree d of a vertex or face in a graph G is the number of incident edges. A face f=v1…vd in a plane or torus graph G is of type (k1,k2,…,kd) if d(vi)⩽ki for 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. It follows from the classical theorem of Lebesgue (1940) that every plane quadrangulation with δ⩾3 has a face of one of the types (3,3,3,∞), (3,3,4,11), (3,3,5,7), (3,4,4,5). Recently, we improved this description to the following one: "(3,3,3,∞), (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 δ⩾3 has a face of one of the following types: (3,3,3,∞), (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 δ⩾5 has a face of one of the types (5,5,8), (5,6,7), or (6,6,6), where all parameters are best possible.
The first author' work was supported by the Ministry of Science
and Higher Education of the Russian Federation (project no.
0314-2019-0016). The second author's work was supported by the
Ministry of Science and Higher Education of the Russian Federation
(Grant No. FSRG-2020-0006).
Поступила28 октября 2021 г., опубликована 1 декабря 2021 г.
Образец цитирования:
O. V. Borodin, A. O. Ivanova, “Tight description of faces in torus triangulations with minimum degree 5”, Сиб. электрон. матем. изв., 18:2 (2021), 1475–1481