Menu
We define the class of \({hereditary \; clique-Helly \; graphs}\) 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.