<p>The dynamic graph coloring problem, an important variant of the classic graph coloring problem, demands the assignment of colors to vertices within a dynamic setting, ensuring that no two adjacent vertices share the same color. This problem holds considerable practical significance, as numerous real-world scenarios can be modeled as dynamic graphs, thus underscoring the critical need for robust solutions. Two main factors influence the effectiveness of solutions: the initial solution during the static process and the recoloring method during the dynamic process. Existing approaches often face limitations by either achieving high efficiency with unsatisfactory solutions or generating high-quality solutions with low efficiency. The primary aim of this research is to balance the efficiency and solution quality in addressing dynamic graph coloring challenges. Specifically, we introduce an incremental algorithm grounded in graph reduction to address the dynamic coloring of large-scale graphs. Our approach leverages the maximum independent set rule to simplify the graph, followed by k-core decomposition and saturation sorting techniques to produce an initial solution of high quality. When the graph undergoes structural modifications, an adaptive recoloring algorithm is employed to recolor it with minimal computational efforts. Comparative results against state-of-the-art dynamic graph coloring algorithms reveal that our approach achieves a superior balance between the number of colors utilized and computational efficiency, surpassing existing methods while maintaining consistent coloring. Moreover, we have designed and implemented a parallel version of the algorithm, further enhancing its computational efficiency.</p>