Intersection graphs for "conflicting" directed paths in trees - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T10:55:25Z http://mathoverflow.net/feeds/question/89863 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89863/intersection-graphs-for-conflicting-directed-paths-in-trees Intersection graphs for "conflicting" directed paths in trees Falk Hüffner 2012-02-29T12:44:42Z 2012-02-29T14:30:06Z <p>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.</p> http://mathoverflow.net/questions/89863/intersection-graphs-for-conflicting-directed-paths-in-trees/89871#89871 Answer by Joseph O'Rourke for Intersection graphs for "conflicting" directed paths in trees Joseph O'Rourke 2012-02-29T13:52:38Z 2012-02-29T14:30:06Z <p>This may count only as a "similar setting," but Martin Golumbic has studied what he calls the <em>edge intersection graph</em> 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 "<em>EPT</em>" graphs, under various assumptions (e.g., on vertex degrees). Here are three references:</p> <ul> <li><p>M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, <em>Discrete Mathematics</em> 55 (1985), 151-159. (<a href="http://www.sciencedirect.com/science/article/pii/0012365X85900433" rel="nofollow">Elsevier link</a>)</p></li> <li><p>Golumbic, Lipshteyn, and Stern, "Representing Edge Intersection Graphs of Paths on Degree 4 Trees," <em>Discrete Mathematics</em>, 2008. (<a href="http://www.deepdyve.com/lp/elsevier/representing-edge-intersection-graphs-of-paths-on-degree-4-trees-0Hf1tVf1z8" rel="nofollow">DeepDyve link</a>).</p></li> <li><p>Golumbic, Lipshteyn, and Stern, "The k-edge intersection graphs of paths in a tree," <em>Discrete Applied Mathematics</em>, Volume 156, Issue 4, 2008. (<a href="http://www.sciencedirect.com/science/article/pii/S0166218X07003101" rel="nofollow">Elsevier link</a>)</p></li> </ul>