The structure of graphs not admitting a fixed immersion
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4104981 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3198033 (Why is no real title available?)
- A minimum degree condition forcing complete graph immersion
- A note on forbidding clique immersions
- A polynomial algorithm for the min-cut linear arrangement of trees
- Call routing and the ratcatcher
- Cutwidth I: A linear time fixed parameter algorithm
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- Cutwidth of split graphs and threshold graphs
- Forbidding Kuratowski graphs as immersions
- Graph coloring and the immersion order
- Graph minors XXIII. Nash-Williams' immersion conjecture
- Graph minors. V. Excluding a planar graph
- Graphs with small bandwidth and cutwidth
- Immersing small complete graphs
- Linear connectivity forces large complete bipartite minors: an alternative approach
- List-coloring graphs without subdivisions and without immersions
- On H‐immersions
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- Polynomial treewidth forces a large grid-like-minor
Cited in
(41)- Packing and covering immersion-expansions of planar sub-cubic graphs
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- Constructing graphs with no immersion of large complete graphs
- Computing partial hypergraphs of bounded width
- Problems hard for treewidth but easy for stable gonality
- Edge-treewidth: algorithmic and combinatorial properties
- Planar graphs having no proper 2-immersions in the plane. II
- Biclique immersions in graphs with independence number 2
- A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
- Edge degeneracy: algorithmic and structural results
- Excluding graphs as immersions in surface embedded graphs
- Cutwidth: obstructions and algorithmic aspects
- The immersion-minimal infinitely edge-connected graph
- The power of cut-based parameters for computing edge-disjoint paths
- A note on forbidding clique immersions
- Lift-contractions
- Lean Tree-Cut Decompositions: Obstructions and Algorithms
- Recent techniques and results on the Erdős-Pósa property
- The structure of graphs with no W4 immersion
- A structure theorem for strong immersions
- Characterising bounded expansion by neighbourhood complexity
- Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
- Spined categories: generalizing tree-width beyond graphs
- Packing and covering immersions in 4-edge-connected graphs
- Packing and covering immersion models of planar subcubic graphs
- On structural parameterizations of the bounded-degree vertex deletion problem
- On objects dual to tree-cut decompositions
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- A weak immersion relation on graphs and its applications
- The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
- Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
- Coloring immersion-free graphs
- Characterizing graphs of small carving-width
- On structural parameterizations of the bounded-degree vertex deletion problem
- Immersion in four-edge-connected graphs
- scientific article; zbMATH DE number 7765417 (Why is no real title available?)
- A note on clique immersion of strong product graphs
- Algorithmic applications of tree-cut width
- A Menger-like property of tree-cut width
- Algorithmic applications of tree-cut width
- Slim tree-cut width
This page was built for publication: The structure of graphs not admitting a fixed immersion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q473098)
