Given an undirected tree and a set of directed paths in this tree (or equivalently, ordered $s$–$t$ pairs), we construct a graph with the paths as vertices and an edge between two paths if they traverse an edge of the tree in opposite directions. Is anything known about the resulting graphs? I found some similar settings, but none that exactly matches. Is this class equivalent to a known one, or does it have interesting characterizations or properties? The only thing I could find is that these graphs cannot have a $K_4$ as subgraph.


This may count only as a "similar setting," but Martin Golumbic has studied what he calls the edge intersection graph of a tree $T$, which has a node for each path in $T$, and an arc between two nodes if their paths share at least one edge. So his paths are not directed. He and coauthors have established a number of structural, coloring, and complexity properties of these "EPT" graphs, under various assumptions (e.g., on vertex degrees). Here are three references:

  • M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Mathematics 55 (1985), 151-159. (Elsevier link)

  • Golumbic, Lipshteyn, and Stern, "Representing Edge Intersection Graphs of Paths on Degree 4 Trees," Discrete Mathematics, 2008. (DeepDyve link).

  • Golumbic, Lipshteyn, and Stern, "The k-edge intersection graphs of paths in a tree," Discrete Applied Mathematics, Volume 156, Issue 4, 2008. (Elsevier link)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.