Vertex partitions of chordal graphs

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

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 contracting 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 ⌊kl(ℓ + 1)⌋-tree. An analogous result is proved for oriented k-trees.
Original languageEnglish
Pages (from-to)167-172
Number of pages6
JournalJournal of Graph Theory
Volume53
Issue number2
DOIs
Publication statusPublished - 2006
Externally publishedYes

Cite this