Recognizing Clique-Helly Graphs

Jayme L.Szwarcfiter1
1 Universidade Federal do Rio de Janeiro Niicleo de Computagio Eletrénica and Instituto de Matematica Caixa Postal 2324, 20001 Rio de Janeiro RJ, Brasil

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.