A Menger-like property of tree-cut width

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

doi:10.1016/j.jctb.2020.12.005

A Menger-like property of tree-cut width

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

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	1-22
Number of pages	22
Journal	Journal of Combinatorial Theory. Series B
Volume	148
DOIs	https://doi.org/10.1016/j.jctb.2020.12.005
State	Published - May 2021

Keywords

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

Access to Document

10.1016/j.jctb.2020.12.005

Cite this

@article{020f28388a044b75b34c900deef4a875,

title = "A Menger-like property of tree-cut width",

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.",

keywords = "Connectivity, Edge-disjoint paths, Graph immersions, Lean decompositions, Linked decompositions, Tree-cut width",

author = "Giannopoulou, {Archontia C.} and Kwon, {O. joung} and Raymond, {Jean Florent} and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2021",

month = may,

doi = "10.1016/j.jctb.2020.12.005",

language = "English (US)",

volume = "148",

pages = "1--22",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - A Menger-like property of tree-cut width

AU - Giannopoulou, Archontia C.

AU - Kwon, O. joung

AU - Raymond, Jean Florent

AU - Thilikos, Dimitrios M.

PY - 2021/5

Y1 - 2021/5

N2 - 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.

AB - 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.

KW - Connectivity

KW - Edge-disjoint paths

KW - Graph immersions

KW - Lean decompositions

KW - Linked decompositions

KW - Tree-cut width

UR - http://www.scopus.com/inward/record.url?scp=85098048141&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85098048141&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2020.12.005

DO - 10.1016/j.jctb.2020.12.005

M3 - Article

AN - SCOPUS:85098048141

SN - 0095-8956

VL - 148

SP - 1

EP - 22

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

A Menger-like property of tree-cut width

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this