Characterization and recognition of generalized clique-Helly graphs Original Research Article

Let image and image be integers. A family of sets image is image-intersecting when every subfamily image formed by p or less members has total intersection of cardinality at least q. A family of sets image is image-Helly when every image-intersecting subfamily image has total intersection of cardinality at least q. A graph G is a image-clique-Helly graph when its family of (maximal) cliques is image-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case image. In this work we present a characterization for image-clique-Helly graphs. For fixed image, this characterization leads to a polynomial-time recognition algorithm. When p or q is not fixed, it is shown that the recognition of image-clique-Helly graphs is NP-hard.