Irreducible triangulations of surfaces with boundary (Q2637719)

Let \(S\) be a surface, possibly with boundary. A triangulation of \(S\) is said to be irreducible if it has no edge whose contraction results in a triangulation of \(S\). For a surface \(S\) with no boundary, \textit{D. W. Barnette} and \textit{A. L. Edelson} [Isr. J. Math. 67, No. 1, 123--128 (1989; Zbl 0689.57008)] showed that \(S\) has a finite number of irreducible triangulations by giving an upper bound on the number of irreducible triangulations in terms of the Euler genus \(g\) of \(S\). Several authors improved this upper bound, with \textit{G. Joret} and \textit{D. R. Wood} giving the currently best bound of \(\max\{13g-4,4\}\) in [J. Comb. Theory, Ser. B 100, No. 5, 446--455 (2010; Zbl 1203.05035)]. In the present paper, the authors consider irreducible triangulations of surfaces with boundary. It is shown that if \(S\) is a surface of Euler genus \(g\) with \(b\) boundary components, and \(g\geq1\) or \(b\geq2\), then an irreducible triangulation of \(S\) has at most \(570g+385b-573\) vertices, except for the case when \((g,b)=(1,0)\) in which case the bound is 186. The authors are able to improve their bound for surfaces without boundary, although the resulting bound is weaker than Joret and Wood's.