
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$.
Computational Theory and Mathematics, 05C70, FOS: Mathematics, Mathematics - Combinatorics, Geometry and Topology, Combinatorics (math.CO), Theoretical Computer Science
Computational Theory and Mathematics, 05C70, FOS: Mathematics, Mathematics - Combinatorics, Geometry and Topology, Combinatorics (math.CO), Theoretical Computer Science
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 31 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
