Seeing the Graphs through the Trees

Abstract

The classical clique-tree/intersection-graph approach to chordal graphs -- along with several applications of chordal graphs -- is based on tree representations whose nodes are the maximal complete subgraphs. This has recently been extended to strongly chordal graphs, and both the original and extended versions are now being generalized to similar tree structures for other classes of graphs, using tree representations whose nodes are other sorts of subgraphs (e.g., neighborhoods). This leads to parallel characterizations for a variety of well-studied graph classes.