Entanglements

Johannes Carmesin; Jan Kurkofka

doi:10.1016/j.jctb.2023.08.007

Entanglements

Johannes Carmesin^*, Jan Kurkofka

^*Corresponding author for this work

Mathematics

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

33 Downloads (Pure)

Abstract

Robertson and Seymour constructed for every graph G a tree-decomposition that efficiently distinguishes all the tangles in G. While all previous constructions of these decompositions are either iterative in nature or not canonical, we give an explicit one-step construction that is canonical.

The key ingredient is an axiomatisation of ‘local properties’ of tangles. Generalisations to locally finite graphs and matroids are also discussed

Original language	English
Pages (from-to)	17-28
Number of pages	12
Journal	Journal of Combinatorial Theory. Series B
Volume	164
Early online date	13 Sept 2023
DOIs	https://doi.org/10.1016/j.jctb.2023.08.007
Publication status	Published - 1 Jan 2024

Keywords

Entanglement
Tree of tangles
Nested set of separations
Efficiently distinguish
Canonical

Access to Document

10.1016/j.jctb.2023.08.007Licence: Creative Commons: Attribution (CC BY)

Carmesin2023_EntaglementsFinal published version, 354 KBLicence: Creative Commons: Attribution (CC BY)

https://linkinghub.elsevier.com/retrieve/pii/S0095895623000680

Graph Minors in three dimensions and Connectivity
Carmesin, J.
Engineering & Physical Science Research Council
1/09/20 → 31/08/25
Project: Research Councils

Cite this

@article{d8a30dcfde02436fbb5c247b326e3839,

title = "Entanglements",

abstract = "Robertson and Seymour constructed for every graph G a tree-decomposition that efficiently distinguishes all the tangles in G. While all previous constructions of these decompositions are either iterative in nature or not canonical, we give an explicit one-step construction that is canonical.The key ingredient is an axiomatisation of {\textquoteleft}local properties{\textquoteright} of tangles. Generalisations to locally finite graphs and matroids are also discussed",

keywords = "Entanglement, Tree of tangles, Nested set of separations, Efficiently distinguish, Canonical",

author = "Johannes Carmesin and Jan Kurkofka",

year = "2024",

month = jan,

day = "1",

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

language = "English",

volume = "164",

pages = "17--28",

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

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Entanglements

AU - Carmesin, Johannes

AU - Kurkofka, Jan

PY - 2024/1/1

Y1 - 2024/1/1

N2 - Robertson and Seymour constructed for every graph G a tree-decomposition that efficiently distinguishes all the tangles in G. While all previous constructions of these decompositions are either iterative in nature or not canonical, we give an explicit one-step construction that is canonical.The key ingredient is an axiomatisation of ‘local properties’ of tangles. Generalisations to locally finite graphs and matroids are also discussed

AB - Robertson and Seymour constructed for every graph G a tree-decomposition that efficiently distinguishes all the tangles in G. While all previous constructions of these decompositions are either iterative in nature or not canonical, we give an explicit one-step construction that is canonical.The key ingredient is an axiomatisation of ‘local properties’ of tangles. Generalisations to locally finite graphs and matroids are also discussed

KW - Entanglement

KW - Tree of tangles

KW - Nested set of separations

KW - Efficiently distinguish

KW - Canonical

UR - https://arxiv.org/abs/2205.11488

U2 - 10.1016/j.jctb.2023.08.007

DO - 10.1016/j.jctb.2023.08.007

M3 - Article

SN - 0095-8956

VL - 164

SP - 17

EP - 28

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Entanglements

Abstract

Keywords

Access to Document

Fingerprint

Projects

Graph Minors in three dimensions and Connectivity

Cite this