Edge and vertex intersection of paths in a tree

DOI10.1016/0012-365X(85)90043-3zbMath0568.05023MaRDI QIDQ1060226

Martin Charles Golumbic, Robert E. Jamison

Publication date: 1985

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

EPT graphedge intersection graphpath graph of a tree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38)

Related Items (41)

NeST graphs ⋮ Intersection graphs of paths in a tree ⋮ Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid ⋮ Parameterized Maximum Path Coloring ⋮ Graphs of edge-intersecting and non-splitting paths ⋮ Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I ⋮ Characterizing width two for variants of treewidth ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Helly EPT graphs on bounded degree trees: characterization and recognition ⋮ Subpath acyclic digraphs ⋮ Tree representations of graphs ⋮ Intersection graphs of orthodox paths in trees ⋮ Parameterized maximum path coloring ⋮ Constant threshold intersection graphs of orthodox paths in trees ⋮ Clustering on trees ⋮ Parameterized complexity of path set packing ⋮ On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid ⋮ A Refined Analysis of Online Path Coloring in Trees ⋮ The recognition of triangle graphs ⋮ Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On spectrum assignment in elastic optical tree-networks ⋮ Inapproximability and approximability of minimal tree routing and coloring ⋮ The \(k\)-edge intersection graphs of paths in a tree ⋮ Subtree and substar intersection numbers ⋮ Representing edge intersection graphs of paths on degree 4 trees ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ On the complexity of recognizing directed path families ⋮ Constant tolerance intersection graphs of subtrees of a tree ⋮ Conversion of coloring algorithms into maximum weight independent set algorithms ⋮ Recognizing Helly edge-path-tree graphs and their clique graphs ⋮ Edge intersection graphs of single bend paths on a grid ⋮ Dyadic representations of graphs ⋮ Equivalences and the complete hierarchy of intersection graphs of paths in a tree ⋮ Recognizing vertex intersection graphs of paths on bounded degree trees ⋮ The edge intersection graphs of paths in a tree ⋮ Interval graphs and related topics ⋮ Triangulated edge intersection graphs of paths in a tree ⋮ Decomposition by clique separators ⋮ Recognition algorithm for intersection graphs of edge disjoint paths in a tree ⋮ Strong cliques and equistability of EPT graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The edge intersection graphs of paths in a tree
• Triangulated edge intersection graphs of paths in a tree
• Decomposition by clique separators
• A recognition algorithm for the intersection graphs of paths in trees
• Intersection representations of graphs by arcs
• On cycle bases of a graph
• A Theorem on Coloring the Lines of a Network

This page was built for publication: Edge and vertex intersection of paths in a tree