Hands-On Software Engineering with Golang

Graph coloring

The next graph-based problem that we will be trying to solve using our graph processing system is graph coloring. The idea behind graph coloring is to assign a color to each vertex in the graph so that no adjacent vertices have the same color. The following diagram illustrates an example graph whose vertices have been colored with the optimal (minimum possible) number of colors:

Figure 3: A graph with optimal coloring

Graph coloring has numerous real-world applications:

• It is frequently used by compilers to perform register allocation ^[2].
• Mobile operators use graph coloring as the means for solving the frequency assignment ...