Tree-cut width is a graph parameter introduced by Wollan that is an analogue of treewidth for the immersion order on graphs in the following sense: the tree-cut width of a graph is functionally equivalent to the largest size of a wall that can be found in it as an immersion. In this work we propose a variant of the definition of tree-cut width that is functionally equivalent to the original one, but for which we can state and prove a tight duality theorem relating it to naturally defined dual objects: appropriately defined brambles and tangles. Using this result we also propose a game characterization of tree-cut width.
翻译:树切宽度是 Wollan 引入的图形参数,它是图中浸入顺序的树丝线的模拟物:图的树切宽度在功能上相当于墙上的最大大小,可以作为浸入。在这项工作中,我们提出了一个树切宽度定义的变量,该变量在功能上与原始宽度相等,但我们可以说明并证明与自然定义的双重对象(适当定义的条纹和三角形)相关联的紧密两极性理论。我们利用这一结果还提出了树切宽度的游戏定性。