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.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
2
|
|
|
|
|
1
|
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:
|
|||
|
|
