A KURATOWSKI THEOREM FOR ORIENTABLE SURFACES

Abstract

Let $SIGMA$ denote a 2-dimensional surface. A graph $G$ is irreducible for $SIGMA$ provided that $G$ does not embed into $SIGMA$, but every proper subgraph of $G$ does. Let $I$($SIGMA$) denote the set of graphs with vertex degree at least three that are irreducible for $SIGMA$. In this paper we prove that $I$($SIGMA$) is finite for each orientable surface. Together with the result by D. Archdeacon and Huneke, stating that $I$($SIGMA$) is finite for each non-orientable surface, this settles a conjecture of Erd$o dotdot$'s from the 1930s that $I$($SIGMA$) is finite for each surface $SIGMA$. Let $SIGMA sub n$ denote the closed orientable surface of genus $n$. We also write $gamma$($SIGMA$) to denote the genus of orientable surface $SIGMA$. Let $G$ be a finite graph. An embedding of $G$ into a surface $SIGMA$ is a topological map \o'0 /'$:G -> SIGMA$. The orientable genus $gamma$($G$) of the graph $G$ is defined to be the least value of $gamma$($SIGMA$) for all orientable surfaces $SIGMA$ into which $G$ can be embedded. Let $P$ be a property of a graph $G$. We say that $G$ is $P$-critical provided that $G$ has property $P$ but no proper subgraph of $G$ has property $P$. For example, if $P$ is the property that $gamma$($G$) $>= 1$, then the $P$-critical graphs are the two Kuratowski graphs $K sub 5$ and $K sub 3,3$. In general, if $P$ is the property that $gamma$($G$) $>= n$, then a $P$-critical graph can be embedded in $SIGMA sub n$ but not in $SIGMA sub {n - 1}$. Such a $P$-critical graph is also called irreducible for the surface $SIGMA sub {n - 1}$. For any surface $SIGMA$, let $I$($SIGMA$) denote the set of graphs that have no vertices of degree two and are irreducible for $SIGMA$.