2006/02/28 by David R. Wood
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Frequency partition of a graph #Graph #Graph Labeling and Dimension Problems #Graph partition #Graph power #Line graph #Mathematical analysis #Mathematics #Partition (number theory) #Tree (set theory) #Upper and lower bounds #Vertex (graph theory) #math.CO #msc:05C70
paper · pdf · doi:10.1016/j.ejc.2008.11.010
published as European J. Combinatorics 30:1245-1253, 2009
arxiv created 2008/01/16 · openalex publication_date 2009/01/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A 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 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 [J. Graph Theory, 1995] proved that every graph with tree-width k≥3 and maximum degree Δ≥1 has tree-partition-width at most 24kΔ. We prove that this bound is within a constant factor of optimal. In particular, for all k≥3 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≥3.