Graphs with few cliques

The phrase “graphs with few cliques” does not correspond to a single, formally defined concept that is widely recognized in the mathematical literature on graph theory. While numerous research papers investigate properties of graphs that contain a limited number of cliques—such as bounds on the total number of cliques in an $n$-vertex graph (e.g., Moon–Moser theorem), extremal results concerning graphs with few maximal cliques, or algorithmic studies of sparse‑clique graphs—there is no standard definition or dedicated entry under this exact terminology in major encyclopedic sources.

Possible contextual interpretations

1. Bounded number of cliques
   The term may be used informally to describe a class of graphs in which the total count of (not necessarily maximal) cliques is bounded by a function of the number of vertices, e.g., graphs that contain at most $O(n)$ cliques.

2. Few maximal cliques
   In algorithmic contexts, “few cliques” is sometimes shorthand for “few maximal cliques,” referring to graphs where the number of inclusion‑wise maximal complete subgraphs is small (often polynomial in the number of vertices). Such graphs admit more efficient enumeration algorithms for maximal cliques.

3. Small clique number
   Occasionally the phrase might be interpreted as “graphs whose largest clique is small,” i.e., graphs with a low clique number $\omega(G)$. This interpretation, however, focuses on the size of the largest clique rather than the overall count.

4. Extremal graph theory
   Results such as the Moon–Moser bound ($2^{n/3}$ maximal cliques in an $n$-vertex graph) or Turán-type theorems discuss the maximal possible number of cliques under various constraints, and papers may refer to “graphs with few cliques” when studying families that fall far below these extremal limits.

Conclusion

Because “graphs with few cliques” lacks a precise, universally accepted definition, it is not treated as an established encyclopedic entry. The phrase is typically employed descriptively in research to denote graphs that satisfy one of the informal notions listed above.