×

zbMATH — the first resource for mathematics

A short proof that every finite graph has a tree-decomposition displaying its tangles. (English) Zbl 1343.05145
Summary: We give a short proof that every finite graph (or matroid) has a tree-decomposition that displays all maximal tangles.
This theorem for graphs is a central result of the graph minors project of N. Robertson and P. D. Seymour [J. Comb. Theory, Ser. B 52, No. 2, 153–190 (1991; Zbl 0764.05069)] and the extension to matroids is due to J. Geelen et al. [J. Comb. Theory, Ser. B 99, No. 4, 657–667 (2009; Zbl 1229.05070)].

MSC:
05C83 Graph minors
05B35 Combinatorial aspects of matroids and geometric lattices
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
Keywords:
graph minors
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] J. Carmesin, All graphs have tree-decompositions displaying their topological ends. Preprint 2014, available at http://arxiv.org/pdf/1409.6640v4.
[2] Carmesin, J.; Diestel, R.; Hamann, M.; Hundertmark, F., Canonical tree decompositions of finite graphs I: existence and algorithms, J. Combin. Theory Ser. B, 116, 1-24, (2016) · Zbl 1327.05269
[3] R. Diestel, F. Hundertmark, S. Lemanczyk, Profiles of separations in graphs and matroids. Preprint 2016, available at http://www.math.uni-hamburg.de/home/diestel/papers/ProfilesNew.pdf. · Zbl 1438.05040
[4] Geelen, Jim; Gerards, Bert; Whittle, Geoff, Tangles, tree-decompositions and grids in matroids, J. Combin. Theory Ser. B, 99, 4, 657-667, (2009) · Zbl 1229.05070
[5] Robertson, N.; Seymour, P. D., Graph minors. X. obstructions to tree-decompositions, J. Combin. Theory Ser. B, 52, 153-190, (1991) · Zbl 0764.05069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.