Abstract:
The degree $d(x)$ of a vertex or face $x$ in a graph $G$ on the plane or other orientable surface is the number of incident edges. A face $f=v_1\ldots v_{d(f)}$ is of type $(k_1,k_2,\dots)$ if $d(v_i)\le k_i$ whenever $1\le i\le d(f)$. We denote the minimum vertex-degree of $G$ by $\delta$. The purpose of our paper is to prove that every triangulation with $\delta\ge4$ of the torus, as well as of large enough such a triangulation of any fixed orientable surface of higher genus has a face of one of the types $(4,4,\infty)$, $(4,6,12)$, $(4,8,8)$, $(5,5,8)$, $(5,6,7)$, or $(6,6,6)$, where all parameters are best possible.