Equivalences and the complete hierarchy of intersection graphs of paths in a tree

DOI10.1016/J.DAM.2008.05.019zbMath1228.05215OpenAlexW2172298723MaRDI QIDQ1003465

Marina Lipshteyn, Michal Stern, Martin Charles Golumbic

Publication date: 4 March 2009

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.05.019

zbMATH Keywords

chordal graphsintersection graphsweakly chordal graphspaths of a tree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

Graphs of edge-intersecting and non-splitting paths ⋮ Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2 ⋮ What Is between Chordal and Weakly Chordal Graphs? ⋮ Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I ⋮ Helly EPT graphs on bounded degree trees: characterization and recognition ⋮ Intersection graphs of orthodox paths in trees ⋮ Constant threshold intersection graphs of orthodox paths in trees ⋮ The vertex leafage of chordal graphs ⋮ Recognising the overlap graphs of subtrees of restricted trees is hard ⋮ Representing edge intersection graphs of paths on degree 4 trees ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Recognizing vertex intersection graphs of paths on bounded degree trees ⋮ Intersection models of weakly chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The edge intersection graphs of paths in a tree
• Edge and vertex intersection of paths in a tree
• Connectivity threshold for random chordal graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Efficient graph representations
• Constant tolerance intersection graphs of subtrees of a tree
• A characterisation of rigid circuit graphs
• Algorithmic graph theory and perfect graphs
• Tolerance intersection graphs on binary trees with constant tolerance 3
• The \(k\)-edge intersection graphs of paths in a tree
• The intersection graphs of subtrees in trees are exactly the chordal graphs

This page was built for publication: Equivalences and the complete hierarchy of intersection graphs of paths in a tree