On Tree-Partition-Width
| dc.creator | Wood, David R. | |
| dc.date | 2006-02-22 | |
| dc.date | 2008-01-16 | |
| dc.date.accessioned | 2026-07-07T12:58:39Z | |
| dc.date.available | 2026-07-07T12:58:39Z | |
| dc.description | A \emph{tree-partition} of a graph $G$ is a proper partition of its vertex set into `bags', such that identifying the vertices in each bag produces a forest. The \emph{tree-partition-width} of $G$ is the minimum number of vertices in a bag in a tree-partition of $G$. An anonymous referee of the paper by Ding and Oporowski [\emph{J. Graph Theory}, 1995] proved that every graph with tree-width $k\geq3$ and maximum degree $Δ\geq1$ has tree-partition-width at most $24kΔ$. We prove that this bound is within a constant factor of optimal. In particular, for all $k\geq3$ and for all sufficiently large $Δ$, we construct a graph with tree-width $k$, maximum degree $Δ$, and tree-partition-width at least $(\eighth-ε)kΔ$. Moreover, we slightly improve the upper bound to ${5/2}(k+1)({7/2}Δ-1)$ without the restriction that $k\geq3$. | |
| dc.identifier | https://arxiv.org/abs/math/0602507 | |
| dc.identifier | http://arxiv.org/abs/math/0602507 | |
| dc.identifier | European J. Combinatorics 30:1245-1253, 2009 | |
| dc.identifier | doi:10.1016/j.ejc.2008.11.010 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/225316 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C70 | |
| dc.title | On Tree-Partition-Width | |
| dc.type | text |