Graphclass: clique-Helly

The following definitions are equivalent:
1. The clique hypergraph of G has V(G) as its vertices and the cliques (maximal complete subgraphs) of G as its hyperedges.
A graph is clique-Helly iff its clique hypergraph has the Helly property.
2. An extended triangle of G is the subgraph induced by a triangle T together with all vertices that are adjacent to at least two vertices of T.
A graph is clique-Helly iff every of its extended triangles contains a universal vertex.

This class is fixed under the clique operator. That is, clique-Helly = clique graphs of clique-Helly.

References

[322] [1015] [1387]

Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

[+]Details

[+]Details

[+]Details

Problems

3-Colourability NP-complete [+]Details
Clique NP-complete [+]Details
Clique cover NP-complete [+]Details
Cliquewidth Unbounded [+]Details
Cliquewidth expression Unbounded or NP-complete [+]Details
Colourability NP-complete [+]Details
Cutwidth NP-complete [+]Details
Domination NP-complete [+]Details
Feedback vertex set NP-complete [+]Details
Hamiltonian cycle NP-complete [+]Details
Hamiltonian path NP-complete [+]Details
Independent set NP-complete [+]Details
Recognition Polynomial [+]Details
Treewidth NP-complete [+]Details
Weighted clique NP-complete [+]Details
Weighted feedback vertex set NP-complete [+]Details
Weighted independent set NP-complete [+]Details