Intersection graphs of paths in a tree

The intersection graph for a family of sets is obtained by associating each set with a vertex of the graph and joining two vertices by an edge exactly when their corresponding sets have a nonempty intersection. Intersection graphs arise naturally in many contexts, such as scheduling conflicting events, and have been widely studied.We present a unified framework for studying several classes of intersection graphs arising from families of paths in a tree. Four distinct classes of graphs arise by considering paths to be the sets of vertices or the edges making up the path, and by allowing the underlying tree to be undirected or directed; in the latter case only directed paths are allowed. Two further classes are obtained by requiring the directed tree to be rooted. We introduce other classes of graphs as well. The rooted directed vertex path graphs have been studied by Gavril; the vertex path graphs have been studied by Gavril and Renz; the edge path graphs have been studied by Golumbic and Jamison, Lobb, Syslo, and Tarjan.The main results are a characterization of these graphs in terms of their “clique tree” representations and a unified recognition algorithm. The algorithm repeatedly separates an arbitrary graph by a (maximal) clique separator, checks the form of the resultant nondecomposable “atoms,” and finally checks that each separation step is valid. In all cases, the first two steps can be performed in polynomial time. In all but one case, the final step is based on a certain two-coloring condition and so can be done efficiently; in the other case the recognition problem can be shown to be NP-complete since a certain three-coloring condition is needed.The strength of this unified approach is that it clarifies and unifies virtually all of the important known results for these graphs and provides substantial new results as well. For example, the exact intersecting relationships among these graphs, and between these graphs and chordal and perfect graphs fall out easily as corollaries. A number of other results, such as bounds on the number of (maximal) cliques, related optimization problems on these graphs, etc., are presented along with open problems.