Terry McKee
(Department of Mathematics and Statistics, Wright State University)
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.
|