Clique number

Definition

Let $G$ be a finite graph. The clique number $\omega(G)$ is the largest number of vertices of a clique in $G$.

Remarks

The vertices of a clique need different colours. Thus $\omega(G) \le \chi(G)$, where $\chi(G)$ is the chromatic number. For the complete graph, $\omega(K_n) = n$. For the cycle graph $C_n$ with $n \ge 4$, $\omega(C_n) = 2$. The inequality $\omega(G) \le \chi(G)$ can be strict: for $C_5$, $\omega = 2$ and $\chi = 3$.

Explanations

L1 human

The clique number is the size of the largest group of vertices that are all joined to each other. It gives a lower bound for the number of colours that a graph needs.