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.

DOI: 10.5121/csit.2026.160202