An incremental search heuristic for coloring vertices of a graph (Q2056884)

In this paper, the authors propose an incremental search heuristic (ISH) method for vertex coloring. First, they expound on the greedy coloring by predecessors and list several good orders of vertices for coloring. Then, the authors prove several related theorems about coloring order, by which an algorithm framework ISH is developed. The algorithm is simple and fast. On small sparse graphs, the algorithm can obtain the same or even a few smaller chromatic numbers than other classical algorithms. However, compared with the hybrid genetic algorithm, the accuracy of the algorithm needs to be improved. The algorithm only achieved a smaller chromatic number on one test set, while the genetic algorithm achieved a smaller chromatic number on six test sets. For the entire collection see [Zbl 1465.05002].