Entanglements

05/23/2022
by   Johannes Carmesin, et al.
0

Robertson and Seymour constructed for every graph G a tree-decomposition that efficiently distinguishes all the tangles in G. While all previous constructions of these decompositions are iterative in nature, we give an explicit one-step construction. The key ingredient is an axiomatisation of 'local properties' of tangles. Generalisations to locally finite graphs and matroids are also discussed.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset