Graphs with few cliques

In graph theory, a class of graphs is said to have few cliques if every member of the class has a polynomial number of maximal cliques.

[1] Certain generally NP-hard computational problems are solvable in polynomial time on such classes of graphs,[1][2] making graphs with few cliques of interest in computational graph theory, network analysis, and other branches of applied mathematics.

[3] Informally, a family of graphs has few cliques if the graphs do not have a large number of large clusters.

One can regard a clique as a cluster of vertices, since they are by definition all connected to each other by an edge.

For that reason, limiting the number of possible maximal cliques has computational ramifications for algorithms on graphs or networks.