Speeding-up of Construction Algorithms for the Graph Coloring Problem

The graph coloring problem (GCP) is one of the most important combinatorial optimization problems that has many practical applications. DSATUR and RLF are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. In this paper, we propose a subgraph degree updating method to improve this issue. Experimental results show that the proposed method is faster than the conventional method and LazyRLF, especially for graphs with higher edge density.