The \(k\)-edge intersection graphs of paths in a tree

DOI10.1016/j.dam.2006.06.019zbMath1132.05042OpenAlexW2005481788MaRDI QIDQ2473042

Michal Stern, Martin Charles Golumbic, Marina Lipshteyn

Publication date: 26 February 2008

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

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

zbMATH Keywords

chordal graphscoloringintersection graphspaths of a treeEPT-graphs

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (10)

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 ⋮ Edge-Intersection Graphs of k-Bend Paths in Grids ⋮ Representing edge intersection graphs of paths on degree 4 trees ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Equivalences and the complete hierarchy of intersection graphs of paths in a tree ⋮ Recognizing vertex intersection graphs of paths on bounded degree trees ⋮ Intersection models of weakly chordal graphs ⋮ Path Partitions, Cycle Covers and Integer Decomposition

Cites Work

• The edge intersection graphs of paths in a tree
• Edge and vertex intersection 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
• A characterisation of rigid circuit graphs
• Algorithmic graph theory and perfect graphs
• Tolerance intersection graphs on binary trees with constant tolerance 3
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The NP-Completeness of Edge-Coloring
• A New Algorithm for Generating All the Maximal Independent Sets
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The \(k\)-edge intersection graphs of paths in a tree