2021/03/26 by Łukasz Bożyk, Bożyk, Łukasz, Oscar Defrain +5 · 1 citation
Economics, Econometrics and Finance · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Sports Analytics and Performance
paper · doi:10.48550/arxiv.2103.14667
openalex publication_date 2021/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.