A Menger-like property of tree-cut width

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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1-22
Number of pages22
JournalJournal of Combinatorial Theory. Series B
StatePublished - May 2021


  • Connectivity
  • Edge-disjoint paths
  • Graph immersions
  • Lean decompositions
  • Linked decompositions
  • Tree-cut width

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'A Menger-like property of tree-cut width'. Together they form a unique fingerprint.

Cite this