Tree decompositions with small width, spread, order and degree
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909018768801792 |
|---|---|
| author | Wood, David R. |
| author_facet | Wood, David R. |
| contents | Tree-decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. The main property of tree-decompositions is the width (the maximum size of a bag minus 1). We show that every graph has a tree-decomposition with near-optimal width, where each vertex appears in few bags. In particular, every graph with treewidth $k$ has a tree-decomposition with width at most $14k+13$, where each vertex $v$ appears in at most $\text{deg}(v)+1$ bags. This improves an exponential bound by Ding and Oporowski [1995] to linear, and establishes a conjecture of theirs in a strong sense. In a second result, we show that every graph with treewidth $k$ has a tree-decomposition with width at most $3k-1$, where on average each vertex appears in at most three bags. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_01140 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tree decompositions with small width, spread, order and degree Wood, David R. Combinatorics Discrete Mathematics Tree-decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. The main property of tree-decompositions is the width (the maximum size of a bag minus 1). We show that every graph has a tree-decomposition with near-optimal width, where each vertex appears in few bags. In particular, every graph with treewidth $k$ has a tree-decomposition with width at most $14k+13$, where each vertex $v$ appears in at most $\text{deg}(v)+1$ bags. This improves an exponential bound by Ding and Oporowski [1995] to linear, and establishes a conjecture of theirs in a strong sense. In a second result, we show that every graph with treewidth $k$ has a tree-decomposition with width at most $3k-1$, where on average each vertex appears in at most three bags. |
| title | Tree decompositions with small width, spread, order and degree |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2509.01140 |