On Lower Bounds for Short Noncontractible Cycles in Embedded Graphs

ID
TR-88-02
Authors
Teresa Maria Przytycka and J. H. Przytycki
Publishing date
January 1988
Abstract

Let $C_{g,n}$ be a constant such that for each triangulation of a surface of genus $g$ with a graph of $n$ vertices there exists a noncontractible cycle of length at most $C_{g,n}$. Hutchinson in [H87] conjectures that $C(g,n)$ = $O(\sqrt{n/g})$ for $g > 0$. In this paper, we present a construction of a triangulation which disproves this conjecture.