zbMATH — the first resource for mathematics

Canonical tree-decompositions of finite graphs. I: Existence and algorithms. (English) Zbl 1327.05269
Summary: We construct tree-decompositions of graphs that distinguish all their \(k\)-blocks and tangles of order \(k\), for any fixed integer \(k\). We describe a family of algorithms to construct such decompositions, seeking to maximize their diversity subject to the requirement that they commute with graph isomorphisms. In particular, all the decompositions constructed are invariant under the automorphisms of the graph.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
05C40 Connectivity
Full Text: DOI
[1] J. Carmesin, R. Diestel, M. Hamann, F. Hundertmark, Canonical tree-decompositions of finite graphs II. The parts, Preprint, 2013. · Zbl 1332.05134
[2] J. Carmesin, R. Diestel, M. Hamann, F. Hundertmark, k-Blocks: a connectivity invariant for graphs, Preprint, 2013. · Zbl 1309.05170
[3] Carmesin, J.; Diestel, R.; Hundertmark, F.; Stein, M., Connectivity and tree structure in finite graphs, Combinatorica, 34, 1, 1-35, (2014)
[4] Diestel, R., Graph theory, (2010), Springer · Zbl 1204.05001
[5] Dunwoody, M. J.; Krön, B., Vertex cuts, (2009) · Zbl 1321.05137
[6] Grohe, M.; Marx, D., Structure theorem and isomorphism test for graphs with excluded topological subgraphs, (2011), in: STOC’12
[7] Hundertmark, F., Profiles. an algebraic approach to combinatorial connectivity, (2011)
[8] Robertson, N.; Seymour, P. D., Graph minors. X. obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[9] Tutte, W. T., Graph theory, (1984), Addison-Wesley · Zbl 0554.05001
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.