## The Vertex Coloring Problem

The vertex coloring problem can be stated as follows:

*"Given a graph, G, assign a color to each vertex of the graph so that no two adjacent vertices have the same color."*

As an example, the following figure shows a valid coloring of the graph that was shown in *figure 5.11*:

###### Figure 5.21: Coloring an uncolored graph

Graph coloring has applications in solving a large variety of problems in the real world – making schedules for taxis, solving sudoku puzzles, and creating timetables for exams can all be mapped to finding a valid coloring of the problem, modeled as a graph. However, finding the minimum number of colors required to produce a valid vertex coloring (also called the chromatic number) is known to be an NP-complete problem. Thus, a minor change in the nature of the problem can make a massive difference to its complexity.

As an example of the applications of the graph coloring problem, let's consider the case of sudoku solvers...