On tree-partition-width by Wood

https://www.doi.org/10.1016/j.ejc.2008.11.010

@article{WoodPartition2009,
author = {David R. Wood},
doi = {10.1016/j.ejc.2008.11.010},
issn = {0195-6698},
journaltitle = {European Journal of Combinatorics},
note = {Part Special Issue on Metric Graph Theory},
number = {5},
pages = {1245--1253},
title = {On tree-partition-width},
volume = {30},
year = {2009},
}

• page 1 : tree-partition-width – A graph $H$ is a partition of a graph $G$ if: each vertex of $H$ is a set of vertices of $G$ (called a bag), every evrtex of $G$ is in exactly one bag of $H$, and distinct bags $A$ and $B$ are adjacent in $H$ if and only if there is an edge of $G$ with one endpoint in $A$ and the other endpoint in $B$. The width of a partition is the maximum number of vertices in a bag. … If a forest $T$ is a partition of a graph $G$, then $T$ is a tree-partition of $G$. The tree-partition-width of $G$ … is the minimum width of a tree-partition of $G$.
• page 2 : tree-partition-width upper bounds treewidth by a linear function – $2twp(G) \ge tw(G)+1$
• page 2 : degree treewidth upper bounds tree-partition-width by a computable function and lower bounds it by a polynomial function – $twp(G) \le 24tw(G)\Delta(G)$
• page 2 : degree treewidth upper bounds tree-partition-width by a computable function and lower bounds it by a polynomial function – Theorem 1. … $twp(G) < \frac 52 (tw(G)+1)(\frac 72 \Delta-1)$
• page 2 : degree treewidth upper bounds tree-partition-width by a computable function and lower bounds it by a polynomial function – Theorem 2. … there is a chordal graph $G$ … $twp(G) \ge (\frac 18 - \epsilon)tw(G)\Delta(G).$