×

zbMATH — the first resource for mathematics

Recognizing clique-Helly graphs. (English) Zbl 0933.05127
From author’s abstract: A family of subsets satisfies the Helly property when every subfamily of it, formed by pairwise intersecting subsets has a common element. A graph is clique-Helly when the family of subsets of vertices which induces the maximal cliques of the graph satisfies the Helly property. We describe a characterization of clique-Helly graphs, leading to a polynomial time algorithm for recognizing them.

MSC:
05C75 Structural characterization of families of graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite