## Intersection graphs for “conflicting” directed paths in trees

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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)

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 5, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9478937387466431, "perplexity_flag": "head"}