The (upper) clique number of a finite simple 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 
.
The clique number 
of a graph is equal to the largest exponent
in the graph's clique
polynomial.
The lower clique number 
may be similarly defined as the size of a graph's
smallest maximal clique.
For a simple graph on 
vertices,
 |
(1)
|
where 
is the vertex degree of the 
th graph vertex.
The clique number of a graph is equal to the independence number of the graph complement,
 |
(2)
|
The chromatic number 
of a graph 
is equal to or greater than its clique number 
, i.e.,
 |
(3)
|
The following table lists the clique numbers for some named graphs. The parameter ranges are 
for the complete graph 
, 
for the cycle graph 
, 
for the star graph 
, and 
for the wheel graph 
on 
vertices. The singleton
graph 
has clique number 1.
The following table gives the number 
of nonisomorphic simple graphs having 
vertices and clique number
for small 
, with the lists starting at 
.
 | 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, ... |
."
Acta Math. 182, 105-142, 1999.Sloane, N. J. A.
Sequences