Vertex partitions of chordal graphs

DOI 10.1002/jgt.20183 Abstract: A k-tree is a chordal graph with no (k + 2)-clique. An -tree-partition of a graph G is a vertex partition of G into ‘bags, ’ such that con-tracting each bag to a single vertex gives an -tree (after deleting loops and replacing parallel edges by a single edge). We prove that for all k ≥ ≥ 0, every k-tree has an -tree-partition in which each bag induces a connected k/( + 1)-tree. An analogous result is proved for oriented k-trees. © 200