On Tree-Partition-Width

Abstract

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\ge 3$ and maximum degree $\Delta \ge 1$ has tree-partition-width at most $24k\Delta$. We prove that this bound is within a constant factor of optimal. In particular, for all $k\ge 3$ and for all sufficiently large $\Delta$, we construct a graph with tree-width $k$, maximum degree $\Delta$, and tree-partition-width at least $(\eighth-ε)kΔ$. Moreover, we slightly improve the upper bound to $5/2(k+1)(7/2\Delta -1)$ without the restriction that $k\ge 3$.

References in corpus (5)

• Layout of Graphs with Bounded Tree-Width
• Graph Drawings with Few Slopes
• Really Straight Graph Drawings
• A linear upper bound on the rectilinear crossing number
• Notes on Nonrepetitive Graph Colouring

Cited by in corpus (13)

• Planar graphs have bounded queue-number
• Clustered 3-Colouring Graphs of Bounded Degree
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Notes on Graph Product Structure Theory
• The size-Ramsey number of powers of bounded degree trees
• Orthogonal Tree Decompositions of Graphs
• Surfaces have (asymptotic) dimension 2
• Colouring Strong Products
• Bad News for Chordal Partitions
• Generalization bounds for learning under graph-dependence: A survey
• Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure
• Witnessing Subsystems for Probabilistic Systems with Low Tree Width
• An Efficient Partitioning Oracle for Bounded-Treewidth Graphs