This paper studies a new Robust Graph Coloring (RGC) problem for modelling the uncertain resource constraint assignment problems in supply chain management. Most optimization tasks under uncertainty were studied by the stochastic programming based on the prediction of the future changes. However, in this study, we have another motivation concerning the robustness of the model to deal with various uncertain changes rather than focusing on the prediction of the input. RGC is an extension of the classical graph coloring problem, which maintains the number of colors as a constraint and models the uncertain scenarios based on the edge weight in the graph. A case studies of RGC - Robust Aircraft Assignment is first introduced. Then, several new techniques are proposed to solve such an NP-hard problem approximately, including the partition based encoding, the improvement graph and k-exchange cycle based neighborhood construction and several meta-heuristics including local search, simulated annealing, tabu search and hybrid method. The experimental results show that the above techniques solve the RGC accurately and effectively.