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.

graph
complete graph
Coxeter graph	2
cubical graph	2
cycle graph
Desargues graph	2
dodecahedral graph	2
Dyck graph	2
Folkman graph	2
Frucht graph	3
Grötzsch Graph	2
Heawood graph	2
Herschel graph	2
Icosahedral graph	3
Möbius-Kantor graph	2
octahedral graph	3
Pappus graph	2
Petersen graph	2
star graph	2
tetrahedral graph	4
wheel graph

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, ...

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 ." 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."