Solving Graph Coloring Problem Based On Independent Set

Graph coloring problem is a classic problem in graph theory, it is a classicNP-complete problem in combinatorial optimization problems. The problem with widerange of research and application background, has been applied to engineering andscientific computing, such as time scheduling, register allocation, spectrum allocation,network communications, arranging arrangements, streaming media scheduling. All graphcoloring problem is equivalent to vertex coloring problem to solve, There are two typesalgorithm solving the vertex coloring algorithm which are exact algorithms andapproximation algorithms. Approximation algorithm with the ability to quickly find asolution for solving the graph coloring problem, however, the exact algorithm has anirreplaceable role.The purpose of the vertex coloring problem is coloring the vertexes. Color as themain considerations, accurating the algorithm based on maximal independent set. Thealgorithm turn original problem to sub-problem by obtaining a maximal independent set.For random example, the test results show that the algorithm to the graph with fewernumber of vertices and denser has good results. Vertices as the main considerations,accurating the algorithm based on the vertex selection. The algorithm assign color set foreach vertex and select a vertex as a decision vertex each time. Decision vertex select acolor in the color set for dyeing and the color set update neighbor candidate. Testing thestandard examples show that the algorithm is able to solve some of the examples of thecoloring problem, so it is a better overall algorithm.Based on the above two algorithms, considering the color and vertex of the graph weproposed a hybrid exact algorithm based on independent set. Firstly, Turing Originalcoloring problem into sub-graph coloring problem through a maximal independent set,then the pair graph coloring problem is solved using vertex selection ideas. Random graphtest results show that the algorithm can solve within all80vertex random graph coloringproblem. The test results of GCI international standard examples show that the algorithmachieved very good results for resolved operator cases and unsolved. By comparison withother algorithms, the proposed algorithm is an efficient and potential algorithm.