Hereditary Clique-Helly Graphs

Abstract

We define the class of $hereditaryclique-Hellygraphs$ or HCH $graphs$. It consists of those graphs, where the cliques of every induced subgraph obey the so-called `Helly-property’, namely, the total intersection of every family of pairwise intersecting cliques is nonempty. Several characterization and an $O(|V{|}^2|E|)$ recognition algorithm for HCH graphs $G=(V,E)$ are given. It is shown that the clique graph of every HCH graph is a HCH graph, and that conversely every HCH graph is the clique graph of some HCH graph. Finally, it is shown that HCH graphs $G=(V,E)$ have at most $|E|$ cliques, whence a maximum cardinality clique can be found in time $O(|V||E{|}^2)$ in such a HCH graph.