We combine the two fundamental fixed-order tangle theorems of Robertson and Seymour into a single theorem that implies both, in a best possible way. We show that, for every $k \in \mathbb{N}$, every tree-decomposition of a graph $G$ which efficiently distinguishes all its $k$-tangles can be refined to a tree-decomposition whose parts are either too small to be home to a $k$-tangle, or as small as possible while being home to a $k$-tangle.
Accepted:
Published online:
Keywords: Tree of tangles, tree-decomposition, tangle-tree duality, abstract separation system
Albrechtsen, Sandra 1
CC-BY 4.0
@article{IGT_2026__3__171_0,
author = {Albrechtsen, Sandra},
title = {Optimal trees of tangles: refining the essential parts},
journal = {Innovations in Graph Theory},
pages = {171--206},
year = {2026},
publisher = {Stichting Innovations in Graph Theory},
volume = {3},
doi = {10.5802/igt.21},
language = {en},
url = {https://igt.centre-mersenne.org/articles/10.5802/igt.21/}
}
TY - JOUR AU - Albrechtsen, Sandra TI - Optimal trees of tangles: refining the essential parts JO - Innovations in Graph Theory PY - 2026 SP - 171 EP - 206 VL - 3 PB - Stichting Innovations in Graph Theory UR - https://igt.centre-mersenne.org/articles/10.5802/igt.21/ DO - 10.5802/igt.21 LA - en ID - IGT_2026__3__171_0 ER -
%0 Journal Article %A Albrechtsen, Sandra %T Optimal trees of tangles: refining the essential parts %J Innovations in Graph Theory %D 2026 %P 171-206 %V 3 %I Stichting Innovations in Graph Theory %U https://igt.centre-mersenne.org/articles/10.5802/igt.21/ %R 10.5802/igt.21 %G en %F IGT_2026__3__171_0
Albrechtsen, Sandra. Optimal trees of tangles: refining the essential parts. Innovations in Graph Theory, Volume 3 (2026), pp. 171-206. doi: 10.5802/igt.21
[1] Refining trees of tangles in abstract separation systems: inessential parts, extended version (2023) (arXiv only extended version of [2]) | DOI | Zbl
[2] Refining trees of tangles in abstract separation systems: inessential parts, Comb. Theory, Volume 4 (2024) no. 1, Paper no. 17, 27 pages | Zbl | MR | DOI
[3] Refining tree-decompositions so that they display the k-blocks, J. Graph Theory, Volume 109 (2025) no. 3, pp. 310-314 | DOI | Zbl | MR
[4] Canonical tree-decompositions of finite graphs I. Existence and algorithms, J. Comb. Theory, Ser. B, Volume 116 (2016), pp. 1-24 | DOI | Zbl | MR
[5] Canonical tree-decompositions of finite graphs II. Essential parts, J. Comb. Theory, Ser. B, Volume 118 (2016), pp. 268-283 | DOI | Zbl | MR
[6] Canonical tree-decompositions of a graph that display its -blocks, J. Comb. Theory, Ser. B, Volume 122 (2017), pp. 1-20 | DOI | Zbl | MR
[7] Graph Theory, Springer, 2017 | DOI | Zbl
[8] Abstract separation systems, Order, Volume 35 (2018), pp. 157-170 | MR | DOI | Zbl
[9] Tree sets, Order, Volume 35 (2018), pp. 171-192 | MR | DOI | Zbl
[10] Duality theorems for blocks and tangles in graphs, SIAM J. Discrete Math., Volume 31 (2017) no. 3, pp. 1514-1528 | DOI | Zbl | MR
[11] Point sets and functions inducing tangles of set separations, J. Comb., Volume 15 (2024) no. 3, pp. 283-306 | DOI | Zbl | MR
[12] Structural submodularity and tangles in abstract separation systems, J. Comb. Theory, Ser. A, Volume 167C (2019), pp. 155-180 | DOI | MR | Zbl
[13] Profiles of separations: in graphs, matroids, and beyond, Combinatorica, Volume 39 (2019) no. 1, pp. 37-75 | DOI | MR | Zbl
[14] Tangle-tree duality in graphs, matroids and beyond, Combinatorica, Volume 39 (2019), pp. 879-910 | Zbl | MR | DOI
[15] Tangle-tree duality in abstract separation systems, Adv. Math., Volume 377 (2021), Paper no. 107470, 25 pages | Zbl | MR | DOI
[16] Refining a tree-decomposition which distinguishes tangles, SIAM J. Discrete Math., Volume 31 (2017), pp. 1529-1551 | MR | Zbl | DOI
[17] Graph Minors. X. Obstructions to Tree-Decomposition, J. Comb. Theory, Ser. B, Volume 52 (1991), pp. 153-190 | MR | Zbl | DOI
Cited by Sources: