Partitioning Cliques of Claw-free Strongly Chordal Graphs

In this paper we find a particular partition of the vertex set of claw-free strongly chordal graphs in which each element is a clique, and we show that the adjacency graph of these cliques is a tree. In particular, the presented results imply the existence of an ordering of the vertices, and a corresponding edge orientation, such that each directed path is contained in at most two maximal cliques. As shown by the authors in previous works, this allows to give performance guarantee approximation results on a wide class of optimization problems.