Immersions in highly edge connected graphs

DOI10.1137/130924056MaRDI QIDQ4979853zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Paul Wollan

Publication date 19 June 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1331

zbMATH Keywords

edge connectivityimmersionstree-cut decomposition

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Abstract: We consider the problem of how much edge connectivity is necessary to force a graph G to contain a fixed graph H as an immersion. We show that if the maximum degree in H is D, then all the examples of D-edge connected graphs which do not contain H as a weak immersion must have a tree-like decomposition called a tree-cut decomposition of bounded width. If we consider strong immersions, then it is easy to see that there are arbitrarily highly edge connected graphs which do not contain a fixed clique K_t as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain K_t as a strong immersion.

Recommendations

• Strong immersions and maximum degree
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• Immersion in four-edge-connected graphs
• A structure theorem for strong immersions
• A minimum degree condition forcing complete graph immersion

Cited in

(28)

• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• Complete graph immersions in dense graphs
• Immersing small complete graphs
• The immersion-minimal infinitely edge-connected graph
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Algorithmic applications of tree-cut width
• Slim tree-cut width
• scientific article; zbMATH DE number 7765417 (Why is no real title available?)
• A structure theorem for strong immersions
• On structural parameterizations of the bounded-degree vertex deletion problem
• Strong immersions and maximum degree
• Biclique immersions in graphs with independence number 2
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• Coloring immersion-free graphs
• A minimum degree condition forcing complete graph immersion
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Excluding subdivisions of bounded degree graphs
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Packing and covering immersions in 4-edge-connected graphs
• The power of cut-based parameters for computing edge-disjoint paths
• Immersion in four-edge-connected graphs
• The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
• The complexity of optimizing atomic congestion
• 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: Immersions in highly edge connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979853)