Intersection graphs of Helly families of subtrees
type: Item
instance of: scholarly article
title: Intersection graphs of Helly families of subtrees
zbMATH Open document ID: 0856.05084
DOI: 10.1016/0166-218X(94)00136-2
published in: Discrete Applied Mathematics
publication date: 1996-07-07T00:00:00Z
review text: A Helly family of a graph \(H\) is a family of subtrees of \(H\) such that every subfamily of mutually intersecting subtrees has a nonempty intersection. The author shows that every graph is an intersection graph of a Helly family of subtrees of a graph without triangles.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 897402
zbMATH Keywords: Helly family
zbMATH Keywords: subtrees
zbMATH Keywords: intersection graph
author: Fanica Gavril
reviewed by: Peter Kirschenhofer
MaRDI profile type: Publication
cites work: A linear algorithm for the group path problem on chordal graphs
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: Algorithms on circular-arc graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Generating the maximum spanning trees of a weighted graph
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism
cites work: Efficient reduction for path problems on circular-arc graphs
cites work: Intersection graphs of paths in a tree
cites work: Q4138414
cites work: Triangulated graphs and the elimination process
cites work: On the tree representation of chordal graphs
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: Characterizing circular-arc graphs
cites work: Coloring a Family of Circular Arcs
full work available at URL: 0166-218x(94)00136-2
OpenAlex ID: W2071616675
description: scientific article; zbMATH DE number 897402