Graph coloring problem

Graph coloring problems include the coloring (or labeling) of vertices in a graph.

For example, we want to color a map where the countries which are neighbours don't have the same colors. The problem is to find the minimal number of different colors to apply.