A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge-disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree-like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path-like linear decomposition isolating the high degree vertices.

A structure theorem for strong immersions / Dvořák, Zdeněk; Wollan, PAUL JOSEPH. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - STAMPA. - 83:2(2016), pp. 152-163. [10.1002/jgt.21990]

A structure theorem for strong immersions

WOLLAN, PAUL JOSEPH
2016

Abstract

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge-disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree-like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path-like linear decomposition isolating the high degree vertices.
2016
graph immersion; graph minor; geometry and topology
01 Pubblicazione su rivista::01a Articolo in rivista
A structure theorem for strong immersions / Dvořák, Zdeněk; Wollan, PAUL JOSEPH. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - STAMPA. - 83:2(2016), pp. 152-163. [10.1002/jgt.21990]
File allegati a questo prodotto
File Dimensione Formato  
Wollan_Structure_2016.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 130.01 kB
Formato Adobe PDF
130.01 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/925087
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact