Metric characterizations of proper interval graphs and tree-clique graphs

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When T is a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real line such that no interval contains another. We present here metric characterizations of proper interval graphs and extend them to tree-clique graphs. This is done by demonstrating “local” properties of tree-clique graphs with respect to the subgraphs induced by paths of a compatible tree. © 1996 John Wiley & Sons, Inc.