Chromatic number

Definition

The chromatic number of an undirected graph $G$ is defined as the smallest nonnegative integer $c$ such that the vertex set of $G$ can be partitioned into $c$ disjoint subsets such that the induced subgraph on each subset is the empty subset. In other words, there are no edges between vertices in the same subset.

We often say that $G$ is:

• $c$-colorable if the chromatic number of $G$ is less than or equal to $c$.
• $c$-chromatic if the chromatic number of $G$ is equal to $c$.

The chromatic number of $G$ is denoted either $\gamma (G)$ or $\chi (G)$. The latter notation is sometimes used for the Euler characteristic, which is a different graph invariant.

Particular cases

We consider the case of a graph on a non-empty vertex set.

Number of vertices	Chromatic number	Conclusion
any	1	The graph is an empty graph
any	2	The graph is a non-empty bipartite graph
finite number $n$	$n$	The graph is a complete graph