Abstract: Dynamic spectrum assignment scheme is an effective measure to solve the low utility of spectrum resources in cognitive radio networks. As to the "starvation" problem of cognitive users, a dynamic spectrum assignment algorithm based on graph coloring was proposed with the purpose of maximizing the system access ratio. The utility function was presented on the basis of graph coloring model, and by updating the available matrix, the allocation process could be implemented effectively. Simulation results demonstrated that the proposed algorithm can obtain a high system access ratio and achieve a good tradeoff between throughput and fairness, and it has much more superiority than the existing algorithms.