scientific article; zbMATH DE number 3912430
The intersection graph for a family of sets is obtained by associating each set with a vertex of the graph and joining two vertices by an edge exactly when their corresponding sets have a nonempty intersection. Intersection graphs arise naturally in many contexts, such as scheduling conflicting events, and have been widely studied. We present a unified framework for studying several classes of intersection graphs arising from families of paths in a tree. Four distinct classes of graphs arise by considering paths to be the sets of vertices or the sets of edges making up the path, and by allowing by underlying tree to be undirected or directed; in the latter case only directed paths are allowed. Two further classes are obtained by requiring the directed tree to be rooted. We introduce other classes of graphs as well. The rooted directed vertex path graphs have been studied by Gavril; the vertex path graphs have been studied by Gavril and Renz; the edge path graphs have been studied by Golumbic and Jamison, Lobb, Syslo, and Tarjan. The main results are a characterization of these graphs in terms of their clique tree representations and a unified recognition algorithm. The algorithm repeatedly separates an arbitrary graph by a (maximal) clique separator, checks the form of the resultant nondecomposable atoms, and finally checks that each separation step is valid. In all cases, the first two steps can be performed in polynomial time. In all but one case, the final step is based on a certain two-coloring condition and so can be done efficiently; in the other case the recognition problem can be shown to be NP-complete since a certain three-coloring condition is needed. The strength of this unified approach is that it clarifies and unifies virtually all of the important known results for these graphs and provides substantial new results as well. For example, the exact intersecting relationships among these graphs, and between these graphs and chordal and perfect graphs fall out easily as corollaries. A number of other results, such as bounds on the number of (maximal) cliques, related optimization problems on these graphs, etc., are presented along with open problems.
- Equivalences and the complete hierarchy of intersection graphs of paths in a tree
- Recognition algorithm for intersection graphs of edge disjoint paths in a tree
- Intersection graphs of concatenable subtrees of graphs
- The unimodular intersection problem
- Recognizing clique graphs of directed edge path graphs
- Intersection graphs of vertex disjoint paths in a tree
- Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs
- Families of induced trees and their intersection graphs
- Constant threshold intersection graphs of orthodox paths in trees
- Intersection graphs of non-crossing paths
- A faster algorithm to recognize undirected path graphs
- Intersection graphs of orthodox paths in trees
- Intersection graphs of short paths in a tree
- Hardness and algorithms for variants of line graphs of directed graphs
- Gene clusters as intersections of powers of paths
- scientific article; zbMATH DE number 5763164 (Why is no real title available?)
- Représentations en arbre de proximités relatives
- Characterizing path graphs by forbidden induced subgraphs
- scientific article; zbMATH DE number 125465 (Why is no real title available?)
- Clique Graphs of Chordal and Path Graphs
- Intersection graphs of proper subtrees of unicyclic graphs
- On the tree-degree of graphs
- scientific article; zbMATH DE number 4116559 (Why is no real title available?)
- scientific article; zbMATH DE number 4117862 (Why is no real title available?)
- scientific article; zbMATH DE number 867646 (Why is no real title available?)
- DV-model that can be rooted
- Strong pseudo transitivity and intersection graphs
- Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
- On \(H\)-topological intersection graphs
- Intersection graphs of non-crossing paths
- Two new characterizations of path graphs
- Intersection representations of matrices by subtrees and unicycles on graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3689221)