Meike Hatzel, Directed tree-cutwidth and immersions

The first major step towards the graph minor structure theorem by Robertson and Seymour was the grid theorem, a result describing that every graph of large treewidth contains a grid as minor. In 2014 Wollan gave a definition for a tree-like decomposition and a width parameter tree-cutwidth with respect to immersions, a different graph containment relation. He provided results linking this parameter to immersions of large walls. This talk presents a version of this parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth establishing that it is linked to directed immersions of large cylindrical walls.

The presented work is joined with Marcin Briański, Karolina Okrasa, and Michał Pilipczuk.