In this paper, the Robust Graph Coloring Problem (RGCP), an extension of the classical graph coloring, is solved by various meta-heuristics. After discussing the search space encoding and neighborhood structure, several meta-heuristics including genetic algorithm, simulated annealing and tabu search are developed to solve RGCP. The experimental results on various sizes of input graph provide the performance of these meta-heuristics in terms of accuracy and run time.