Tight description of faces in torus triangulations with minimum degree 5

Abstract

The  degree $d(x)$ of a vertex or face $x$ in a graph $G$  is the number of incident edges. A face $f=v_1\ldots v_{d(f)}$ in a plane or torus graph $G$ is of type $(k_1,k_2,\ldots)$  if $d(v_i)\le k_i$ for each $i$. By $\delta$ we denote the  minimum vertex-degree of $G$.  In 1989, Borodin confirmed Kotzig's conjecture of 1963 that every plane graph with minimum degree $\delta$ 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 $\delta\ge3$  has a face of one of the types $(3,3,3,\infty)$, $(3,3,4,11)$, $(3,3,5,7)$, $(3,4,4,5)$. Recently, we improved this description to the following one: ``$(3,3,3,\infty)$, $(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 $\delta\ge3$ has a face of one of the following types:  $(3,3,3,\infty)$, $(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 $\delta\ge5$ has a face of one of the types  $(5,5,8)$, $(5,6,7)$, or $(6,6,6)$, where all parameters are best possible.