A maximal clique is a clique that cannot be extended by including one more adjacent vertex, meaning it is not a subset of a larger clique.
A maximum clique (i.e., clique of largest size
in a given graph) is therefore always maximal, but the converse does not hold.
Maximal cliques are important in graph theoretic applications, including graph coloring, fractional graph coloring, and computation of other graph properties such as intersection
number.
The Bron-Kerbosch algorithm is an efficient method for finding all maximal cliques in a graph. Tomita et al. (2006) gave
a depth-first search algorithm with pruning methods that is similar to the Bron-Kerbosch
algorithm, and the Wolfram Language
can be used to find all maximal cliques in a given graph using this algorithm via
FindClique[g,
Infinity, All].
The polynomial in
whose coefficients of
are the numbers of maximal cliques of size may be called the maximal
clique polynomial. The size of a smallest maximal clique may be termed the lower clique number and the size of a largest
maximal clique (which is equivalent to the size of a maximum
clique) the (upper) clique number.
Akkoyunlu, E. A. "The Enumeration of Maximal Cliques of Large Graphs." SIAM J. Comput.2, 1-6, 1973.Bron,
C. and Kerbosch, J. "Algorithm 457: Finding All Cliques of an Undirected Graph."
Comm. ACM16, 48-50, 1973.Stix, V. "Finding All Maximal
Cliques in Dynamic Graphs." In Computational Optimization and Applications,
Vol. 7. Norwell, MA: Kluwer, 1994.Tomita, E.; Tanaka, A.; and
Takahashi, H. "The Worst-Case Time Complexity for Generating All Maximal Cliques
and Computational Experiments." Theor. Comput. Sci.363, 28-42,
2006.