Tree decompositions and many-sided separations

MaRDI QIDQ6405693zbMATH OpenFDO

Authors Tara Abrishami

Publication date 21 July 2022

Abstract: A separation of a graph $G$ is a partition $(A_1,A_2,C)$ of $V(G)$ such that $A_1$ is anticomplete to $A_2$. A classic result from Robertson and Seymour's Graph Minors Project states that there is a correspondence between tree decompositions and laminar collections of separations. A many-sided separation of a graph $G$ is a partition $(A_1,ldots,A_k,C)$ of $V(G)$ such that $A_i$ is anticomplete to $A_j$ for all $1leqi<jleqk$. In this note, we show a correspondence between tree decompositions with a certain parity property, called deciduous tree decompositions, and laminar collections of many-sided separations.

This page was built for publication: Tree decompositions and many-sided separations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405693)