In this paper, we present multi-threaded algorithms for graph coloring suitable to the shared memory programming model. Initially, we describe shared memory implementations to the algorithms widely known in the literature like Jones Plassman graph coloring. Later, we propose new approaches to solve the problem of coloring using mutex locks while making sure that deadlocks do not occur. Using datasets from real world graphs, we evaluate the performance of all these algorithms on the Intel platform. We compare the performance of sequential graph coloring v/s our proposed approaches and analyze the speedup obtained against the existing algorithms from the literature. The results show that the speedup obtained by our proposed algorithms in terms of the time taken for coloring is consequential. We also provide a direction for future work towards improving the performance further in terms of different metrics. © 2017 ACM.