# Intersection graphs for “conflicting” directed paths in trees

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.

-

## 1 Answer

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)

-