zbMATH — the first resource for mathematics

Hereditary clique-Helly graphs. (English) Zbl 0794.05113
Let \(G= G(V,E)\) be a finite undirected graph. The graphs \(G\) where every clique contains some edge that lies in no other clique form the class of irreducible graphs. The graphs where every induced subgraph is irreducible are called hereditarily irreducible. Moreover, \(G\) is called a clique-Helly graph, if for any set of pairwise intersecting cliques from \(G\), the total intersection of these cliques is not empty, and consequently the class of these graphs is a subclass of the class of irreducible graphs.
A graph is said to be a hereditary clique-Helly graph (HCH graph) if it possesses the property that every induced subgraph is a clique-Helly graph. HCH graphs are characterized by some properties, for instance: (1) The class of HCH graphs is exactly the class of hereditary irreducible graphs. (2) Every strongly chordal graph is a HCH graph. (3) The common neighborhood of any two distance 2 vertices in an HCH graph induces a trivially perfect graph. (4) The clique graph of every HCH graph is a HCH graph, and conversely every HCH graph is the clique graph of some HCH graph. (5) No connected HCH graph has more cliques than edges, and it is shown that the cardinality of a maximum clique can be computed in time \(O(| V|| E|^ 2)\).
The investigations also yield an \(O(| V|^ 2| E|)\)-time recognition algorithm for HCH graphs.

05C75 Structural characterization of families of graphs
05C99 Graph theory