×

Partitioning graphs of bounded tree-width. (English) Zbl 0924.05022

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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C05 Trees
05C55 Generalized Ramsey theory
Full Text: DOI