Parallel graph coloring algorithms are based on the observation that if we split the graph into multiple independent sets of vertices, we can color those in parallel without introducing any conflict.
An independent set is defined as the collection or set of vertices where no two vertices share an edge.
To develop a parallelized version of the sequential greedy graph coloring algorithm from the previous section, we will be relying on a simple, yet effective algorithm proposed by Jones and Plassmann [6]. Before diving into the implementation details, let's take a few minutes to explain how the algorithm generates independent sets and how can we guarantee that our compute function will avoid ...
