Improvement of the DSATUR algorithm for graph coloring

Abstract

In this paper we discuss the deterministic Brelaz's DSATUR algorithm for graph coloring. We propose a simple modification that improves the performance of the algorithm. This modification consists of assigning the color that saturates the least number of uncolored vertices, to the selected vertex. Thus, we obtain valid k-colorings better than those obtained with DSATUR without modification. We show also that the DSATUR algorithm is optimal, for a given example, and for the bipartite graphs.