Refining tree-decompositions so that they display the k-blocks
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910389102444544 |
|---|---|
| author | Albrechtsen, Sandra |
| author_facet | Albrechtsen, Sandra |
| contents | Carmesin and Gollin proved that every finite graph has a canonical tree-decomposition $(T, \mathcal{V})$ of adhesion less than $k$ that efficiently distinguishes every two distinct $k$-profiles, and which has the further property that every separable $k$-block is equal to the unique part of $(T, \mathcal{V})$ in which it is contained.
We give a shorter proof of this result by showing that such a tree-decomposition can in fact be obtained from any canonical tight tree-decomposition of adhesion less than $k$. For this, we decompose the parts of such a tree-decomposition by further tree-decompositions. As an application, we also obtain a generalization of Carmesin and Gollin's result to locally finite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19585 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Refining tree-decompositions so that they display the k-blocks Albrechtsen, Sandra Combinatorics 05C83, 05C40, 05C05, 05C63 Carmesin and Gollin proved that every finite graph has a canonical tree-decomposition $(T, \mathcal{V})$ of adhesion less than $k$ that efficiently distinguishes every two distinct $k$-profiles, and which has the further property that every separable $k$-block is equal to the unique part of $(T, \mathcal{V})$ in which it is contained. We give a shorter proof of this result by showing that such a tree-decomposition can in fact be obtained from any canonical tight tree-decomposition of adhesion less than $k$. For this, we decompose the parts of such a tree-decomposition by further tree-decompositions. As an application, we also obtain a generalization of Carmesin and Gollin's result to locally finite graphs. |
| title | Refining tree-decompositions so that they display the k-blocks |
| topic | Combinatorics 05C83, 05C40, 05C05, 05C63 |
| url | https://arxiv.org/abs/2403.19585 |