Representing edge intersection graphs of paths on degree 4 trees

DOI10.1016/j.disc.2007.07.064zbMath1136.05046OpenAlexW1979264598MaRDI QIDQ2476278

Michal Stern, Marina Lipshteyn, Martin Charles Golumbic

Publication date: 18 March 2008

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

Full work available at URL: https://doi.org/10.1016/j.disc.2007.07.064

zbMATH Keywords

coloringintersection graphsEPT graphsweakly chordal graphspaths of a tree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) 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 ⋮ Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I ⋮ Helly EPT graphs on bounded degree trees: characterization and recognition ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs ⋮ On the bend-number of planar and outerplanar graphs ⋮ On spectrum assignment in elastic optical tree-networks ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Edge intersection graphs of systems of paths on a grid with a bounded number of bends ⋮ Edge intersection graphs of single bend paths on a grid ⋮ Recognizing vertex intersection graphs of paths on bounded degree trees ⋮ Strong cliques and equistability of EPT graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The edge intersection graphs of paths in a tree
• Equivalences and the complete hierarchy of intersection graphs of paths in a tree
• Edge and vertex intersection of paths in a tree
• Triangulated edge intersection graphs of paths in a tree
• Decomposition by clique separators
• A recognition algorithm for the intersection graphs of paths in trees
• Efficient graph representations
• Constant tolerance intersection graphs of subtrees of a tree
• Optimizing weakly triangulated graphs
• 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
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Representing edge intersection graphs of paths on degree 4 trees