A sequential greedy algorithm for coloring undirected graphs

Calculating the optimal graph coloring is known to be NP-hard. Therefore, researchers have proposed greedy algorithms that produce good enough, but not necessarily optimal, solutions. The sequential greedy algorithm listed here works with undirected graphs and guarantees an upper bound of d+1 colors where d is the maximum out-degree (number of outgoing edges) for all the vertices in the graph:

function assignColors(Graph):
  C holds the assigned color for each vertex
  for each vertex u in Graph:
    C[u] = 0

  for each vertex u in Graph:
    already_in_use is a map where keys indicate colors that are currently in use
    for each neighbor v of u:
      already_in_use[ C[v] ] = true

    assigned_color = 1
    while already_in_use[ color ] is true:
     assigned_color = assigned_color + 1

    C[u] = assigned_color

The algorithm maintains an array called C that holds the assigned color for each vertex in the graph. During initialization, we set each entry of the C array to the value 0 to indicate that no color has been assigned to any of the graph vertices.

For each vertex u in the graph, the algorithm iterates its neighbor list and inserts the colors that have been already assigned to each neighbor into a map using the color value as a key. Next, the assigned_color variable is set to the lowest possible color value (in this case, 1) and the already_in_use map is consulted to check whether that color is currently in use. If that happens to be the case, we increment the assigned_color variable and repeat the same steps until we finally land on a color value that is not in use. The unused color value is assigned to vertex u and the process continues until all the vertices have been colored.

An interesting fact about the preceding algorithm is that we can tweak it slightly to add support for handling pre-colored graphs. In this type of graph, a subset of the vertices have been already assigned a color value and the goal is to assign non-conflicting colors to the remaining vertices. All we need to do is the following: