Intersection graphs of Helly families of subtrees

https://doi.org/10.1016/0166-218X(94)00136-2Get rights and content
Under an Elsevier user license
open archive

Abstract

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.

Keywords

Intersection graph of subtrees
Helly family of subtrees
Neighborhood chordal graph
Cactus subtree graph
Circular-arc graph

Cited by (0)