Research work · 2026
A Parallel Graph Coloring Algorithm with Applications in Machine Learning
Maedeh Yahaghi, Saeed Bakhshan
Computer Science and Machine Learning
Abstract
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.