Maedeh Yahaghi and Saeed Bakhshan , Wayne State University ,USA

In this paper we present a parallel algorithm for coloring 3-colorable graphs, based on Wigderson's classical algorithm which guarantees a coloring using at most O(√n) colors. To parallelize the approach, we integrate Luby and Gebremedhin-Manne (GM) algorithm for parallel coloring. Experimental evaluations demonstrate that our parallel algorithm achieves speedup to 16 threads.

Graph Coloring , Parallel Algorithm , Machine Learning