Tree-partitions of graphs with given pathwidth
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916053042331648 |
|---|---|
| author | Wood, David R. |
| author_facet | Wood, David R. |
| contents | Graphs with bounded treewidth and bounded maximum degree are known to have tree-partitions of bounded width. What can be said if the bounded treewidth assumption is strengthened to bounded pathwidth? We prove that every graph with bounded pathwidth and bounded maximum degree has a tree-partition of bounded width, with the extra property that the underlying tree has bounded pathwidth. Moreover, we prove a lower bound showing that the bound on the pathwidth of the underlying tree is within a constant factor of optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_27780 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tree-partitions of graphs with given pathwidth Wood, David R. Combinatorics Discrete Mathematics Graphs with bounded treewidth and bounded maximum degree are known to have tree-partitions of bounded width. What can be said if the bounded treewidth assumption is strengthened to bounded pathwidth? We prove that every graph with bounded pathwidth and bounded maximum degree has a tree-partition of bounded width, with the extra property that the underlying tree has bounded pathwidth. Moreover, we prove a lower bound showing that the bound on the pathwidth of the underlying tree is within a constant factor of optimal. |
| title | Tree-partitions of graphs with given pathwidth |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2605.27780 |