Irreducible Triangulations are Small

Abstract

A triangulation of a surface is \emph{irreducible} if there is no edge whose contraction produces another triangulation of the surface. We prove that every irreducible triangulation of a surface with Euler genus $g\ge 1$ has at most $13g-4$ vertices. The best previous bound was $171g-72$.

v2: Referees' comments incorporated

Cited by in corpus (5)

• Subgraph densities in a surface
• The maximum number of cliques in a graph embedded in a surface
• Irreducible triangulations of surfaces with boundary
• Edge-Maximal Graphs on Surfaces
• A fast algorithm for computing irreducible triangulations of closed surfaces in $E^d$