Edge and vertex intersection of paths in a tree
From MaRDI portal
The path graph of a tree T is a graph whose vertex set is the set \({\mathcal P}\) of nontrivial simple paths in T and in which two vertices are adjacent if and only if they (as paths) have a common vertex. Similarly the edge intersection graph of paths (shortly EPT graph) of a tree T is defined; its vertex set is again \({\mathcal P}\) and two vertices are adjacent in it if and only if they have a common edge. First a theorem on maximal cliques of an EPT graph is proved. Further the authors present a characterization of graphs which are simultaneously path graphs and EPT graphs of some trees. At the end it is proved that recognizing whether a given graph is an EPT graph is an NP-complete problem.
Recommendations
Cites work
- A recognition algorithm for the intersection graphs of paths in trees
- A Theorem on Coloring the Lines of a Network
- Decomposition by clique separators
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3639680 (Why is no real title available?)
- Intersection representations of graphs by arcs
- On cycle bases of a graph
- The edge intersection graphs of paths in a tree
- Triangulated edge intersection graphs of paths in a tree
Cited in
(56)- Equivalences and the complete hierarchy of intersection graphs of paths in a tree
- A superclass of edge-path-tree graphs with few cliques
- Integrality properties of edge path tree families
- Interval graphs and related topics
- Triangulated edge intersection graphs of paths in a tree
- Decomposition by clique separators
- Intersection graphs of paths in a tree
- Algorithmic aspects of intersection graphs and representation hypergraphs
- Representations of graphs and networks (coding, layouts and embeddings)
- Recognition algorithm for intersection graphs of edge disjoint paths in a tree
- Clustering on trees
- NeST graphs
- On spectrum assignment in elastic optical tree-networks
- Towards a comprehensive theory of conflict-tolerance graphs
- Constant tolerance intersection graphs of subtrees of a tree
- Conversion of coloring algorithms into maximum weight independent set algorithms
- Dyadic representations of graphs
- Intersection graphs of vertex disjoint paths in a tree
- Subpath acyclic digraphs
- Constant threshold intersection graphs of orthodox paths in trees
- Recognizing Helly edge-path-tree graphs and their clique graphs
- Helly EPT graphs on bounded degree trees: characterization and recognition
- Intersection graphs of orthodox paths in trees
- The k-edge intersection graphs of paths in a tree
- Representing edge intersection graphs of paths on degree 4 trees
- Strong cliques and equistability of EPT graphs
- On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
- Intersection graphs of short paths in a tree
- Graphs of edge-intersecting non-splitting paths in a tree: towards hole representations (extended abstract)
- Graphs of edge-intersecting and non-splitting paths
- Parameterized maximum path coloring
- A refined analysis of online path coloring in trees
- Edge intersection graphs of single bend paths on a grid
- Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
- Edge and vertex intersection of paths in a graph
- Characterizing width two for variants of treewidth
- scientific article; zbMATH DE number 5763164 (Why is no real title available?)
- Parameterized maximum path coloring
- The recognition of triangle graphs
- Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. II
- Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
- EPT graphs on bounded degree trees
- Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
- Parameterized complexity of path set packing
- On local edge intersection graphs of paths on bounded degree trees
- Characterizations and clique coloring of edge intersection graphs on a triangular grid
- Subtree and substar intersection numbers
- Parameterized complexity of path set packing
- Relationship among B₁-EPG, VPT and EPT graphs classes
- Clique coloring EPT graphs on bounded degree trees
- Exact algorithms for edge deletion to Cactus
- Recognizing vertex intersection graphs of paths on bounded degree trees
- The edge intersection graphs of paths in a tree
- Tree representations of graphs
- Inapproximability and approximability of minimal tree routing and coloring
- On the complexity of recognizing directed path families
This page was built for publication: Edge and vertex intersection of paths in a tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1060226)
