Intersection graphs of Helly families of subtrees Original Research Article

A graph is called neighborhood chordal if the neighborhood of every vertex is chordal. A family of subtrees of a graph is called 2-acyclic if the union of any two subtrees is acyclic. In the present paper we prove that every graph is an intersection graph of a Helly family of subtrees of a graph without triangles. In particular, we prove that a graph 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 simple greedy algorithm to construct the corresponding family of subtrees. In addition, we describe polynomial-time recognition algorithms for the intersection graphs and for the perfect intersection graphs of Helly families of subtrees in cacti graphs.