INTERSECTION GRAPHS OF HELLY FAMILIES OF SUBTREES

A graph is called neighborhood chordal if the neighborhood of every ve rtex is chordal. A family of subtrees of a graph is called 2-acyclic i f the union of any two subtrees is acyclic. In the present paper we pr ove that every graph is an intersection graph of a Helly family of sub trees of a graph without triangles. In particular, we prove that a gra ph is an intersection graph of a Helly 2-acyclic family of subtrees of a graph iff it is neighborhood chordal, in which case we present a si mple greedy algorithm to construct the corresponding family of subtree s. In addition, we describe polynomial-time recognition algorithms for the intersection graphs and for the perfect intersection graphs of He lly families of subtrees in cacti graphs.