= Clique number
{title2=$\omega(G)$}
The <clique number> $\omega(G)$ is the maximum number of <vertices> in a <clique> of a finite <graph>:
$$
\omega(G)=\max\{|C|:C\text{ is a clique in }G\}.
$$
We use $\omega(G)=0$ for the <graph> with no <vertices>. For a nonempty <complete graph>, $\omega(K_n)=n$; for the five-<vertex> example, $\omega(G)=3$.
If the <graph> contains $K_k$ and no $K_{k+1}$ as <subgraphs>, its <clique number> is exactly $k$, because every larger <clique> contains a <clique> with $k+1$ <vertices>. Also $\chi(G)\geq\omega(G)$: a <proper vertex coloring> must assign different colors to all members of any <clique>. This lower bound need not be an equality; the <cycle graph> $C_5$ has <clique number> $2$ and <chromatic number> $3$.
Back to article page
