A KURATOWSKI THEOREM FOR ORIENTABLE SURFACES
Date
1987-12-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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$.
Description
Keywords
Computer Science