A Matrix Approach to Dynamic Coloring Problem
Meirong Xu, Liying Sun · 2021
A dynamic coloring of a graph ${\mathcal{G}}$ is a proper coloring such that for each vertex v with degree at least 2, the neighbors of v receive at least two different colors. This paper investigates the dynamic coloring problem and presents a number of new results and algorithms. By defining a logical operator and using the semi-tensor product method, four necessary and sufficient conditions are proposed for the solvability of the dynamic coloring problem, based on which a new algorithm to find all the feasible dynamic coloring schemes for any simple graph is put forward. Moreover, one illustrative example is studied to show the effectiveness of the results/algorithms presented in this paper.