A Menger-like property of tree-cut width

DOI10.1016/J.JCTB.2020.12.005zbMATH Open1459.05260arXiv1808.00863OpenAlexW3117235601MaRDI QIDQ1998754FDOQ1998754

Jean-Florent Raymond, Dimitrios M. Thilikos, O-joung Kwon, Archontia C. Giannopoulou

Publication date: 8 March 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain vertex-connectivity condition called leanness [A Menger-like property of tree-width: The finite case. Journal of Combinatorial Theory, Series B, 48(1):67-76, 1990]. This result had many uses and has been extended to several other decompositions. In this paper, we consider tree-cut decompositions, that have been introduced by Wollan as a possible edge-version of tree decompositions [The structure of graphs not admitting a fixed immersion. Journal of Combinatorial Theory, Series B, 110:47-66, 2015]. We show that every graph admits a tree-cut decomposition of minimum width that additionally satisfies an edge-connectivity condition analogous to Thomas' leanness.

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

zbMATH Keywords

edge-disjoint pathsconnectivitytree-cut widthgraph immersionslean decompositionslinked decompositions

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• $k$-Blocks: A Connectivity Invariant for Graphs
• Typical subgraphs of 3- and 4-connected graphs
• The edge-density for \(K_{2,t}\) minors
• Graph minors. V. Excluding a planar graph
• Branch-width and Rota's conjecture
• Rank-width and vertex-minors
• The structure of graphs not admitting a fixed immersion
• Branch-width and well-quasi-ordering in matroids and graphs.
• Graph minors. IV: Tree-width and well-quasi-ordering
• Rank-Width and Well-Quasi-Ordering
• Tournament minors
• A Menger-like property of tree-width: The finite case
• Upper bounds on the size of obstructions and intertwines
• Linked tree-decompositions of represented infinite matroids
• Directed width parameters and circumference of digraphs
• An FPT 2-approximation for tree-cut decomposition
• Algorithmic Applications of Tree-Cut Width
• Cutwidth: obstructions and algorithmic aspects
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• A unified treatment of linked and lean tree-decompositions
• Linear Rank-Width of Distance-Hereditary Graphs

Cited In (5)

• Title not available (Why is that?)
• Slim tree-cut width
• Faster parameterized algorithms for modification problems to minor-closed classes
• On objects dual to tree-cut decompositions
• Title not available (Why is that?)

This page was built for publication: A Menger-like property of tree-cut width

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