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.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.