The structure of graphs not admitting a fixed immersion
From MaRDI portal
Publication:473098
DOI10.1016/J.JCTB.2014.07.003zbMATH Open1302.05148arXiv1302.3867OpenAlexW2074101363MaRDI QIDQ473098FDOQ473098
Authors: Paul Wollan 
Publication date: 21 November 2014
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1302.3867
Recommendations
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Call routing and the ratcatcher
- Graph minors. V. Excluding a planar graph
- Polynomial treewidth forces a large grid-like-minor
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- Graph coloring and the immersion order
- Immersing small complete graphs
- Title not available (Why is that?)
- A minimum degree condition forcing complete graph immersion
- Graph minors XXIII. Nash-Williams' immersion conjecture
- A polynomial algorithm for the min-cut linear arrangement of trees
- Cutwidth I: A linear time fixed parameter algorithm
- On H‐immersions
- A note on forbidding clique immersions
- Title not available (Why is that?)
- Graphs with small bandwidth and cutwidth
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- Forbidding Kuratowski graphs as immersions
- Cutwidth of split graphs and threshold graphs
- List-coloring graphs without subdivisions and without immersions
- Linear connectivity forces large complete bipartite minors: an alternative approach
Cited In (41)
- Cutwidth: obstructions and algorithmic aspects
- A note on forbidding clique immersions
- Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
- The immersion-minimal infinitely edge-connected graph
- A Menger-like property of tree-cut width
- A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
- The structure of graphs with no W4 immersion
- Characterising bounded expansion by neighbourhood complexity
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Algorithmic applications of tree-cut width
- Slim tree-cut width
- Packing and covering immersion models of planar subcubic graphs
- Title not available (Why is that?)
- A structure theorem for strong immersions
- On structural parameterizations of the bounded-degree vertex deletion problem
- Biclique immersions in graphs with independence number 2
- Excluding graphs as immersions in surface embedded graphs
- Spined categories: generalizing tree-width beyond graphs
- Packing and covering immersion-expansions of planar sub-cubic graphs
- Edge-treewidth: algorithmic and combinatorial properties
- Planar graphs having no proper 2-immersions in the plane. II
- Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
- Characterizing graphs of small carving-width
- Coloring immersion-free graphs
- The power of cut-based parameters for computing edge-disjoint paths
- Packing and covering immersions in 4-edge-connected graphs
- A note on clique immersion of strong product graphs
- Problems hard for treewidth but easy for stable gonality
- Constructing graphs with no immersion of large complete graphs
- Immersion in four-edge-connected graphs
- On objects dual to tree-cut decompositions
- Lift-contractions
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- Lean Tree-Cut Decompositions: Obstructions and Algorithms
- Computing partial hypergraphs of bounded width
- Edge degeneracy: algorithmic and structural results
- Recent techniques and results on the Erdős-Pósa property
- On structural parameterizations of the bounded-degree vertex deletion problem
- The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
- Algorithmic applications of tree-cut width
- A weak immersion relation on graphs and its applications
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)
