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$-chromatic if the chromatic number is less than or equal to $c$.

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