The first application to these cases is the minimum graph coloring problem. This is a very well known problem, in which giving a graph we want to assign to each node of he graph a color such that two of the edge nodes have different colors. And of course we want to use the minimum number of colors.

---