Comparing trees characteristic to chordal and dually chordal graphs

Abstract

Chordal and dually chordal graphs possess characteristic tree representations, namely, clique trees and compatible trees, respectively. The following problem is studied: given a chordal graph G, it has to be determined if the clique trees of G are exactly the compatible trees of K(G). This does not always happen. A necessary and sufficient condition so that it is true, in terms of the minimal vertex separators of the graph, is found.