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

DOI10.1016/J.DAM.2008.05.019MaRDI QIDQ1003465zbMATH OpenOpenAlexFDO

Authors Martin Charles Golumbic, Marina Lipshteyn, Michal Stern

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

intersection graphschordal graphsweakly chordal graphspaths of a tree

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3912430
• Intersection graphs of paths in a tree
• scientific article; zbMATH DE number 4116559
• The \(k\)-edge intersection graphs of paths in a tree
• The edge intersection graphs of paths in a tree
• scientific article; zbMATH DE number 5763164
• Intersection graphs of orthodox paths in trees
• Intersection graphs of vertex disjoint paths in a tree
• Intersection graphs of short paths in a tree
• Intersection graphs of concatenable subtrees of graphs

Cites work

• scientific article; zbMATH DE number 5763164 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 2170450 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• A characterisation of rigid circuit graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Algorithmic graph theory and perfect graphs
• Connectivity threshold for random chordal graphs
• Constant tolerance intersection graphs of subtrees of a tree
• Constant tolerance representations of graphs in trees
• Edge and vertex intersection of paths in a tree
• Efficient graph representations
• The \(k\)-edge intersection graphs of paths in a tree
• The edge intersection graphs of paths in a tree
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tolerance intersection graphs on binary trees with constant tolerance 3

Cited in

(15)

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

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

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