A Menger-like property of tree-cut width

DOI10.1016/J.JCTB.2020.12.005MaRDI QIDQ1998754zbMATH OpenOpenAlexFDO

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

Publication date 8 March 2021

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

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)

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.

Recommendations

• A unified treatment of linked and lean tree-decompositions
• A Menger-like property of tree-width: The finite case
• scientific article; zbMATH DE number 1870231
• The structure of graphs not admitting a fixed immersion
• The Menger-like property of the three-width of infinite graphs

Cites work

• scientific article; zbMATH DE number 1870231 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Menger-like property of tree-width: The finite case
• A unified treatment of linked and lean tree-decompositions
• Algorithmic applications of tree-cut width
• Branch-width and Rota's conjecture
• Branch-width and well-quasi-ordering in matroids and graphs.
• Cutwidth: obstructions and algorithmic aspects
• Directed width parameters and circumference of digraphs
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. V. Excluding a planar graph
• Linear kernels for edge deletion problems to immersion-closed graph classes
• Linear rank-width of distance-hereditary graphs
• Linked tree-decompositions of represented infinite matroids
• Rank-Width and Well-Quasi-Ordering
• Rank-width and vertex-minors
• The edge-density for \(K_{2,t}\) minors
• The structure of graphs not admitting a fixed immersion
• Tournament minors
• Typical subgraphs of 3- and 4-connected graphs
• Upper bounds on the size of obstructions and intertwines
• \(k\)-blocks: a connectivity invariant for graphs

Cited in

(8)

• scientific article; zbMATH DE number 1870231 (Why is no real title available?)
• A unified treatment of linked and lean tree-decompositions
• Slim tree-cut width
• Faster parameterized algorithms for modification problems to minor-closed classes
• A Menger-like property of tree-width: The finite case
• On objects dual to tree-cut decompositions
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• scientific article; zbMATH DE number 7471715 (Why is no real title available?)

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)