Immersions in highly edge connected graphs

DOI10.1137/130924056zbMATH Open1292.05158arXiv1305.1331OpenAlexW1980529780MaRDI QIDQ4979853FDOQ4979853

Authors: Dániel Marx, Paul Wollan 

Publication date: 19 June 2014

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

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.

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

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

zbMATH Keywords

edge connectivityimmersionstree-cut decomposition

Mathematics Subject Classification ID

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

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
• The immersion-minimal infinitely edge-connected graph
• Immersing small complete graphs
• 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
• Title not available (Why is that?)
• A structure theorem for strong immersions
• Strong immersions and maximum degree
• On structural parameterizations of the bounded-degree vertex deletion problem
• 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
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Excluding subdivisions of bounded degree graphs
• A minimum degree condition forcing complete graph immersion
• The power of cut-based parameters for computing edge-disjoint paths
• Packing and covering immersions in 4-edge-connected graphs
• 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)