Canonical tree-decompositions of finite graphs I. Existence and algorithms

Johannes Carmesin; Reinhard Diestel; Matthias Hamann; Fabian Hundertmark

doi:10.1016/j.jctb.2014.04.001

Canonical tree-decompositions of finite graphs I. Existence and algorithms

Johannes Carmesin, Reinhard Diestel, Matthias Hamann, Fabian Hundertmark

Mathematics

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

236 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	1-24
Journal	Journal of Combinatorial Theory. Series B
Volume	116
Early online date	28 Aug 2015
DOIs	https://doi.org/10.1016/j.jctb.2014.04.001
Publication status	Published - Jan 2016

Bibliographical note

23 pages, 5 figures

Keywords

math.CO
graph
connectivity
tree-decomposition
k-block
tangle
profile
Tutte-decomposition

Access to Document

10.1016/j.jctb.2014.04.001Licence: None: All rights reserved

Carmesin_et_al_Canonical_tree-decompositions_Journal_of_Combinatorial_Theory_Series_B_2016Submitted manuscript, 1.18 MBLicence: None: All rights reserved

Cite this

@article{0e2f21420aa942589d7e75e2c038b31b,

title = "Canonical tree-decompositions of finite graphs I. Existence and algorithms",

abstract = "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. ",

keywords = "math.CO, graph, connectivity, tree-decomposition, k-block, tangle, profile, Tutte-decomposition",

author = "Johannes Carmesin and Reinhard Diestel and Matthias Hamann and Fabian Hundertmark",

note = "23 pages, 5 figures",

year = "2016",

month = jan,

doi = "10.1016/j.jctb.2014.04.001",

language = "English",

volume = "116",

pages = "1--24",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Canonical tree-decompositions of finite graphs I. Existence and algorithms

AU - Carmesin, Johannes

AU - Diestel, Reinhard

AU - Hamann, Matthias

AU - Hundertmark, Fabian

N1 - 23 pages, 5 figures

PY - 2016/1

Y1 - 2016/1

N2 - 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.

AB - 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.

KW - math.CO

KW - graph

KW - connectivity

KW - tree-decomposition

KW - k-block

KW - tangle

KW - profile

KW - Tutte-decomposition

U2 - 10.1016/j.jctb.2014.04.001

DO - 10.1016/j.jctb.2014.04.001

M3 - Article

SN - 0095-8956

VL - 116

SP - 1

EP - 24

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Canonical tree-decompositions of finite graphs I. Existence and algorithms

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this