Excluding Graphs as Immersions in Surface Embedded Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

Excluding Graphs as Immersions in Surface Embedded Graphs

Résumé

We prove a structural characterization of graphs that forbid a fixed graph $H$ as an immersion and can be embedded in a surface of Euler genus $\gamma$. In particular, we prove that a graph $G$ that excludes some connected graph $H$ as an immersion and is embedded in a surface of Euler genus $\gamma$ has either "small" treewidth (bounded by a function of $H$ and $\gamma$) or "small" edge connectivity (bounded by the maximum degree of $H$). Using the same techniques we also prove an excluded grid theorem on bounded genus graphs for the immersion relation.

Dates et versions

lirmm-00805139 , version 1 (27-03-2013)

Identifiants

  • HAL Id : lirmm-00805139 , version 1
  • ARXIV : 1303.6567

Citer

Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos. Excluding Graphs as Immersions in Surface Embedded Graphs. 2013. ⟨lirmm-00805139⟩
97 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More