Intersection graphs of vertex disjoint paths in a tree

DOI10.1016/0012-365X(94)00163-9MaRDI QIDQ1903730zbMATH OpenFDO

Authors B. S. Panda, Saraju P. Mohanty

Publication date 23 April 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00163-9

zbMATH Keywords

algorithmclique separatorsintersection graphspathtree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

The paper characterizes the intersection graphs of internally vertex disjoint path in a tree in terms of maximal clique separators and by forbidden subgraphs and presents an algorithm recognizing these graphs in time \(O(n^4m)\).

Recommendations

• Recognition algorithm for intersection graphs of edge disjoint paths in a tree
• Two new characterizations of path graphs
• scientific article; zbMATH DE number 4116559
• scientific article; zbMATH DE number 3912430
• Edge and vertex intersection of paths in a tree

Cites work

• A characterisation of rigid circuit graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• A slice genus lower bound from \(sl(n)\) Khovanov-Rozansky homology
• Decomposition by clique separators
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• Intersection graphs of paths in a tree
• Intersection representations of graphs by arcs
• Representations of chordal graphs as subtrees of a tree
• The edge intersection graphs of paths in a tree
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Triangulated edge intersection graphs of paths in a tree

Cited in

(14)

• Equivalences and the complete hierarchy of intersection graphs of paths in a tree
• A linear time recognition algorithm for proper interval graphs
• Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction
• The forbidden subgraph characterization of directed vertex graphs
• Recognition algorithm for intersection graphs of edge disjoint paths in a tree
• Intersection graphs of non-crossing paths
• A faster algorithm to recognize undirected path graphs
• Intersection graphs of short paths in a tree
• Edge and vertex intersection of paths in a graph
• scientific article; zbMATH DE number 5763164 (Why is no real title available?)
• scientific article; zbMATH DE number 4116559 (Why is no real title available?)
• Truly non-trivial graphoidal graphs
• Intersection graphs of non-crossing paths
• Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms

This page was built for publication: Intersection graphs of vertex disjoint paths in a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1903730)