Edge and vertex intersection of paths in a tree

Abstract

In this paper we continue the investigation of the class of edge intersection graphs of a collection of paths in a tree (EPT graphs) where two paths edge intersect if they share an edge. The class of EPT graphs differs from the class known as path graphs, the latter being the class of vertex intersection graphs of paths in a tree. A characterization is presented here showing when a path graph is an EPT graph. In particular, the classes of path graphs and EPT graphs coincide on trees all of whose vertices have degree at most 3. We then prove that it is an NP-complete problem to recognize whether a graph is an EPT graph. © 1985.