A Menger-like property of tree-cut width
2021
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. 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 (2015) as a possible edge-version of tree decompositions. We show that every graph admits a tree-cut decomposition of minimum width that additionally satisfies an edge-connectivity condition analogous to Thomas' leanness.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
28
References
1
Citations
NaN
KQI