Intersection graphs of Helly families of subtrees
From MaRDI portal
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.
Recommendations
Cites work
- A linear algorithm for the group path problem on chordal graphs
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- A New Algorithm for Generating All the Maximal Independent Sets
- Algorithms on circular-arc graphs
- Characterizing circular-arc graphs
- Coloring a Family of Circular Arcs
- Efficient reduction for path problems on circular-arc graphs
- Generating the maximum spanning trees of a weighted graph
- scientific article; zbMATH DE number 3566474 (Why is no real title available?)
- Intersection graphs of paths in a tree
- On the tree representation of chordal graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Complexity of Coloring Circular Arcs and Chords
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Triangulated graphs and the elimination process
Cited in
(16)- Intersection graphs of concatenable subtrees of graphs
- Algorithms for maximum weight induced paths
- Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs
- Families of induced trees and their intersection graphs
- Intersection graphs of \(k\)-acyclic families of subtrees and relational database query processing.
- Helly type theorem and graphs
- Revisiting Tucker's algorithm to color circular-arc graphs
- Maximum weight independent sets and cliques in intersection graphs of filaments
- scientific article; zbMATH DE number 1002178 (Why is no real title available?)
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- Approximation algorithms for maximum weight k-coverings of graphs by packings
- On \(H\)-topological intersection graphs
- Intersection graphs of non-crossing paths
- Maximum max-k-clique subgraphs in cactus subtree graphs
- Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
- Intersection representations of matrices by subtrees and unicycles on graphs
This page was built for publication: Intersection graphs of Helly families of subtrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917300)
