Complete minors in orientable surfaces

Gašper Fijavž
IMFM and University of Ljubljana

PDF

Minisymposium: GRAPH IMBEDDINGS AND MAP SYMMETRIES

Content: Assume that a graph $G$ embeds in a surface $\Sigma$. A theorem of Robertson and Seymour states that there exists a constant $c_\Sigma$, so that every graph which embeds in $\Sigma$ with face-width $\ge c_\Sigma$ contains $G$ as a minor. Let $\Sigma$ be an arbitrary \emph{orientable} surface of genus $\ge 1$. We prove that there exists an absolute constant $c$ (independent on the choice of $\Sigma$), so that: \begin{itemize} \item if $G$ embeds in $\Sigma$ with face-width $\ge c$, then $G$ contains a $K_7$ minor, and \item if $G$ is not bipartite and embeds in $\Sigma$ with face-width $\ge c$ while having all faces of even length, then $G$ contains an \emph{odd} $K_5$ minor. \end{itemize} This is in part joint work with Atsuhiro Nakamoto.

Back to all abstracts