We present an easy structure theorem for graphs which do not admit an immersion of the complete graph. The theorem motivates the definition of a variation of tree decompositions based on edge cuts instead of vertex cuts which we call tree-cut decompositions. We give a definition for the width of tree-cut decompositions, and using this definition along with the structure theorem for excluded clique immersions, we prove that every graph either has bounded tree-cut width or admits an immersion of a large wall.

The structure of graphs not admitting a fixed immersion / Wollan, PAUL JOSEPH. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - STAMPA. - 110:(2015), pp. 47-66. [10.1016/j.jctb.2014.07.003]

The structure of graphs not admitting a fixed immersion

WOLLAN, PAUL JOSEPH
2015

Abstract

We present an easy structure theorem for graphs which do not admit an immersion of the complete graph. The theorem motivates the definition of a variation of tree decompositions based on edge cuts instead of vertex cuts which we call tree-cut decompositions. We give a definition for the width of tree-cut decompositions, and using this definition along with the structure theorem for excluded clique immersions, we prove that every graph either has bounded tree-cut width or admits an immersion of a large wall.
2015
Edge disjoint; Immersion; Tree decompositions; Tree-cut decompositions; Discrete Mathematics and Combinatorics; Theoretical Computer Science; Computational Theory and Mathematics
01 Pubblicazione su rivista::01a Articolo in rivista
The structure of graphs not admitting a fixed immersion / Wollan, PAUL JOSEPH. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - STAMPA. - 110:(2015), pp. 47-66. [10.1016/j.jctb.2014.07.003]
File allegati a questo prodotto
File Dimensione Formato  
Wollan_structure_2015.pdf

accesso aperto

Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 355.19 kB
Formato Adobe PDF
355.19 kB Adobe PDF

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/796538
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 54
  • ???jsp.display-item.citation.isi??? 40
social impact