Linked tree-decompositions into finite parts
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916242061787136 |
|---|---|
| author | Albrechtsen, Sandra Jacobs, Raphael W. Knappe, Paul Pitz, Max |
| author_facet | Albrechtsen, Sandra Jacobs, Raphael W. Knappe, Paul Pitz, Max |
| contents | We prove that every graph which admits a tree-decomposition into finite parts has a rooted tree-decomposition into finite parts that is linked, tight and componental.
As an application, we obtain that every graph without half-grid minor has a lean tree-decomposition into finite parts, strengthening the corresponding result by Kriz and Thomas for graphs of finitely bounded tree-width. In particular, it follows that every graph without half-grid minor has a tree-decomposition which efficiently distinguishes all ends and critical vertex sets, strengthening results by Carmesin and by Elm and Kurkofka for this graph class.
As a second application of our main result, it follows that every graph which admits a tree-decomposition into finite parts has a tree-decomposition into finite parts that displays all the ends of $G$ and their combined degrees, resolving a question of Halin from 1977. This latter tree-decomposition yields short, unified proofs of the characterisations due to Robertson, Seymour and Thomas of graphs without half-grid minor, and of graphs without binary tree subdivision. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_06753 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linked tree-decompositions into finite parts Albrechtsen, Sandra Jacobs, Raphael W. Knappe, Paul Pitz, Max Combinatorics 05C63, 05C05, 05C83, 05C40 We prove that every graph which admits a tree-decomposition into finite parts has a rooted tree-decomposition into finite parts that is linked, tight and componental. As an application, we obtain that every graph without half-grid minor has a lean tree-decomposition into finite parts, strengthening the corresponding result by Kriz and Thomas for graphs of finitely bounded tree-width. In particular, it follows that every graph without half-grid minor has a tree-decomposition which efficiently distinguishes all ends and critical vertex sets, strengthening results by Carmesin and by Elm and Kurkofka for this graph class. As a second application of our main result, it follows that every graph which admits a tree-decomposition into finite parts has a tree-decomposition into finite parts that displays all the ends of $G$ and their combined degrees, resolving a question of Halin from 1977. This latter tree-decomposition yields short, unified proofs of the characterisations due to Robertson, Seymour and Thomas of graphs without half-grid minor, and of graphs without binary tree subdivision. |
| title | Linked tree-decompositions into finite parts |
| topic | Combinatorics 05C63, 05C05, 05C83, 05C40 |
| url | https://arxiv.org/abs/2405.06753 |