Clique Number
The clique number of a graph 
, denoted 
, is the number of vertices in a maximum
clique of 
. Equivalently, it is the size of a largest
clique or maximal clique
of 
.
For an arbitrary graph,
 |
where 
is the degree
of graph vertex 
. In addition, the
chromatic number 
of a graph
is equal to or greater than its clique number 
, i.e.,
 |
The following table lists the clique numbers for some named graphs.
The following table gives the number 
of 
-node graphs having
clique number 
for small 
.
 | OEIS |  |
| 1 | 1, 1, 1, 1, 1, 1, 1, 1, ... | |
| 2 | A052450 | 0, 1, 2, 6, 13, 37, 106, 409, 1896, ... |
| 3 | A052451 | 0, 0, 1, 3, 15, 82, 578, 6021, 101267, ... |
| 4 | A052452 | 0, 0, 0, 1, 4, 30, 301, 4985, 142276, ... |
| 5 | A077392 | 0, 0, 0, 0, 1, 5, 51, 842, 27107, ... |
| 6 | A077393 | 0, 0, 0, 0, 0, 1, 6, 80, 1995, ... |
| 7 | A077394 | 0, 0, 0, 0, 0, 0, 1, 7, 117, ... |
| 8 | 0, 0, 0, 0, 0, 0, 0, 1, 8, ... |
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 
."
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."
Weisstein, Eric W. "Clique Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CliqueNumber.html
Contact the MathWorld Team
12! / (4! * 6! * 2!)
