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

partitionscoloringtree-widthstar-forests

Mathematics Subject Classification ID

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

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

(33)

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

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)