Clique Number
The (upper) clique number of a graph G, denoted omega(G), is the number of vertices in a maximum clique of G. Equivalently, it is the size of a largest clique or maximal clique of G.
The clique number omega(G) of a graph is equal to the largest exponent in the graph's clique polynomial.
The lower clique number omega_L(G) may be similarly defined as the size of a graph's smallest maximal clique.
For an arbitrary graph,
where d_i is the vertex degree of i.
The clique number of a graph is equal to the independence number of the complement graph,
| omega(G)=alpha(G^_). |
(2)
|
The chromatic number chi(G) of a graph G is equal to or greater than its clique number omega(G), i.e.,
| chi(G)>=omega(G). |
(3)
|
The following table lists the clique numbers for some named graphs.
The following table gives the number N_k(n) of n-node graphs having clique number k for small k.
See also
Bold Conjecture, Clique Graph, Clique Polynomial, Fractional Clique Number, Independence Number, Maximal Clique, Maximum CliqueExplore with Wolfram|Alpha
More things to try:
References
Aigner, M. "Turán's Graph Theorem." Amer. Math. Monthly 102, 808-816, 1995.Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.Hastad, J. "Clique Is Hard to Approximate Within n^(1-epsilon)." Acta Math. 182, 105-142, 1999.Sloane, N. J. A. Sequences A052450, A052451, A052452, A077392, A077393, and A077394 in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
Clique NumberCite this as:
Weisstein, Eric W. "Clique Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CliqueNumber.html