Decomposition Duality

This is a short note suggesting how tree-decompositions may be generalized to decompositions modelled on other graphs than trees. It turns out that there is a surprising duality between the H-decompositions of a graph G and the G-decompositions of H. This duality generalizes the duality of plane graphs, so the question arises whether properties of the latter such as flow-colouring duality might generalize to this kind of decomposition duality.

Download (DVI; PDF)