Partitioning graphs of bounded tree-width

DOI10.1007/S004930050001MaRDI QIDQ1307308zbMATH OpenOpenAlexFDO

Authors Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Dirk Vertigan

Publication date 31 October 1999

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930050001

zbMATH Keywords

coloringpartitionsstar-foreststree-width

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Review text

This paper studies vertex partitions and edge partitions of graphs of bounded tree-width into graphs of smaller tree-width. First the existence of several kinds of such partitions is proved. Then it is shown that some of the results of the first part are close to being best possible. Finally a result on partitioning graphs of bounded tree-width into star-forests is described.

Recommendations

• On tree-partition-width
• Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size
• Partitioning into graphs with only small components
• On tree-partitions of graphs

Cited in

(35)

• On tree-partition-width
• A partial k-arboretum of graphs with bounded treewidth
• Partitioning into graphs with only small components
• Induced and weak induced arboricities
• Paths between colourings of graphs with bounded tree-width
• Constrained domatic bipartition on trees
• \(\mathcal Q\)-Ramsey classes of graphs
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Block-cutvertex trees and block-cutvertex partitions
• Minimal reducible bounds for induced-hereditary properties
• On tree-partitions of graphs
• Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
• Treewidth of graphs with balanced separations
• Partitioning a weighted tree into subtrees with weights in a given range
• Edge-intersection graphs of grid paths: the bend-number
• Tree partitioning via vertex deletion
• Linear time low tree-width partitions and algorithmic consequences
• On vertex partitions and some minor-monotone graph parameters
• An efficient partitioning oracle for bounded-treewidth graphs
• Simple monadic theories and partition width
• Tree‐based Graph Partitioning Constraint
• scientific article; zbMATH DE number 3866593 (Why is no real title available?)
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
• Vertex partitions of chordal graphs
• Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
• scientific article; zbMATH DE number 5526012 (Why is no real title available?)
• scientific article; zbMATH DE number 6292751 (Why is no real title available?)
• The Size Ramsey Number of Graphs with Bounded Treewidth
• Tree-partitions with bounded degree trees
• Product structure of graph classes with bounded treewidth
• Product structure of graph classes with strongly sublinear separators
• Partitioning complete graphs by heterochromatic trees
• On invariants of hereditary graph properties
• Bounding tree-width via contraction on the projective plane and torus
• Three ways to cover a graph

This page was built for publication: Partitioning graphs of bounded tree-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1307308)