Algorithms for the graph coloring problem

Abstract

The graph coloring problem is known to be in the class of NP-complete problems. Two approaches of solving the problem have been discussed in the past: (1) formulating the problem into a 0-1 integer programming model, which mathematically expresses the feasibility of applying given colors to a graph, and solving the model iteratively using an implicit enumerat ion algorithm; and (2) implicitly enumerating all possible assignments of colors to the vertices. For the first approach, a 0-1 goal programming model is proposed , and an algorithm is constructed to solve the model. The algorithm requires a huge amount of storage; therefore, it is considered to be inferior to existing algorithms which utilize the second approach. However, the theoretical development of the model and the algorithm are discussed at length. For the second approach, a branch-and-bound algorithm is constructed which implicitly enumerates all possible assignments of colors to the vertices. The algorithm is further improved by incorporating a separation method called the range cutting method. The cutting method is shown experimentally to be effective for the graph coloring problem, and therefore, is extensively discussed in application to the integer programming problem. In an attempt to enhance the performance of the branch-and-bound algorithms, a heuristic algorithm modified from t he color-degree algorithm is constructed to generate a range for the optimal solution of the graph coloring problem . The modified algorithm gene rates much narrower ranges than the color-degree algorithm does, thus enhancing the efficiency of the graph coloring algorithms.