The edge intersection graphs of paths in a tree (Q792348)

We investigate 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 cliques of an EPT graph are characterized and shown to have strong Helly number 4. From this we demonstrate that one can find a maximum clique of an EPT graph in polynomial time. We show that the strong perfect graph conjecture holds for EPT graphs. Further complexity results follow from the observation that every line graph is an EPT graph. The class of EPT graphs is equivalent to the class of fundamental cycle graphs.