  In this paper, we present multi-threaded algorithms for graph coloring
suitable to the shared memory programming model. We modify an existing
algorithm widely used in the literature and prove the correctness of the
modified algorithm. We also propose a new approach to solve the problem of
coloring using locks. Using datasets from real world graphs, we evaluate the
performance of the algorithms on the Intel platform. We compare the performance
of the sequential approach v/s our proposed approach and analyze the speedup
obtained against the existing algorithm from the literature. The results show
that the speedup obtained is consequential. We also provide a direction for
future work towards improving the performance further in terms of different
metrics.
