Potatoes and Onions
Abstract
The first major step in the theory of graph minors of Robertson and Seymour was the grid theorem, a fundamental duality result describing that any graph of sufficiently high treewidth must contain a large grid as a minor. Since this pioneering work, multiple grid theorems have been established in structural graph theory, linking various width parameters of combinatorial objects with the non-existence of grid-like obstructions. In particular, Kawarabayashi and Kreutzer [STOC'15] proved a variant of the grid theorem for directed graphs that links directed treewidth with the non-existence of topological minors of large cylindrical walls. On the other hand, to study immersions of undirected graphs − another containment relation that focuses on edge-disjointness, rather than vertex-disjointness − Wollan [JCTB'15] introduced a parameter, tree-cutwidth, and proved that it is dual to immersions of large walls. In this work, we present a version of Wollan's parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth, establishing that it is dual to directed immersions of large cylindrical walls.
BibTeX
@misc{brianski2026potatoes,
title = {{Potatoes and Onions}},
author = {Marcin Briański and Meike Hatzel and Karolina Okrasa and Michał Pilipczuk},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20391},
eprint = {2610.20391},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20391},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Potatoes and Onions
AU - Marcin Briański
AU - Meike Hatzel
AU - Karolina Okrasa
AU - Michał Pilipczuk
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20391
UR - https://arxiv.org/abs/2610.20391
AB - The first major step in the theory of graph minors of Robertson and Seymour was the grid theorem, a fundamental duality result describing that any graph of sufficiently high treewidth must contain a large grid as a minor. Since this pioneering work, multiple grid theorems have been established in structural graph theory, linking various width parameters of combinatorial objects with the non-existence of grid-like obstructions. In particular, Kawarabayashi and Kreutzer [STOC'15] proved a variant of the grid theorem for directed graphs that links directed treewidth with the non-existence of topological minors of large cylindrical walls. On the other hand, to study immersions of undirected graphs − another containment relation that focuses on edge-disjointness, rather than vertex-disjointness − Wollan [JCTB'15] introduced a parameter, tree-cutwidth, and proved that it is dual to immersions of large walls. In this work, we present a version of Wollan's parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth, establishing that it is dual to directed immersions of large cylindrical walls.
ER -