Intersection graphs of vertex disjoint paths in a tree

DOI10.1016/0012-365X(94)00163-9zbMath0837.05094MaRDI QIDQ1903730

B. S. Panda, Saraju P. Mohanty

Publication date: 23 April 1996

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

zbMATH Keywords

treealgorithmpathintersection graphsclique separators

Mathematics Subject Classification ID

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

Related Items (5)

Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Truly non-trivial graphoidal graphs ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• A slice genus lower bound from \(sl(n)\) Khovanov-Rozansky homology
• The edge intersection graphs of paths in a tree
• Triangulated edge intersection graphs of paths in a tree
• Decomposition by clique separators
• Intersection graphs of paths in a tree
• 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 characterisation of rigid circuit graphs
• Intersection representations of graphs by arcs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representations of chordal graphs as subtrees of a tree

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