Mainly to solve the famous four-color conjecture, a concept formed.

The specific mathematical historical materials are as follows:

As early as 19 12, Birkhoff put forward the concept of chromatic polynomial [14- 15] to solve the four-color conjecture. The basic idea of coloring polynomial is: how many coloring methods are there to color a graph with a given number of colors?

The coloring polynomial of graph G is denoted as P(G, x), which represents the number of methods for coloring graphs with no more than x colors. For the integer k, if P(G, k) = 0, it means that the graph g cannot be dyed with only k colors. Chromatic polynomials are closely related to vertex coloring. The chromatic number of a graph is actually the smallest positive integer that makes its chromatic polynomial take a non-zero value. Therefore, if the chromatic polynomial of a graph is found, then the chromatic number of the graph is easy to find.

One of the advantages of studying vertex coloring problems with coloring polynomials is that graph theory problems can be handled with mature algebraic tools. Mathematicians have done a lot of research on colored polynomials, and obtained many research results, such as the famous edge-shrinking principle, which can be used to find the colored polynomials of general graphs. The principle of edge contraction will be described in detail later.

In addition, vertex coloring problem is a typical NP? Difficult problem, now a major problem related to this is: P =? Most mathematicians tend to think that P ≠NP is the NP problem, but this problem is far from being solved in theory [16- 18]. Theoretically, it seems too difficult to completely solve the vertex coloring problem, so far there is no good solution to NP? Method of difficult problem

Although mathematicians have made a lot of achievements, in essence, there is no substantial progress in theory. Because of the need of engineering and practical application, mathematicians and engineers all over the world have done a lot of algorithm research on vertex coloring problem. A large number of approximate algorithms have been proposed, but there are not many accurate algorithms with high efficiency.

In the aspect of approximation algorithm, the simplest algorithm is the color number minimum priority algorithm, which chooses the color with the smallest available color number to dye one point at a time. However, this algorithm can not give an exact solution, and even in most cases, its approximate solution is far from the exact solution. In addition, mathematicians use popular algorithms such as genetic algorithm, heuristic algorithm and distributed algorithm to study vertex coloring, and put forward various approximate algorithms.

For example, Brelaz proposed a genetic algorithm called Brelaz coloring, which can give a good approximate solution. However, all the above approximation algorithms can't get exact solutions. In some practical problems, high-precision approximate solutions are enough to meet the application. This may be the reason why a large number of approximation algorithms have been proposed. In terms of accurate algorithm, the progress is not as good as that of approximate algorithm. One of the more intuitive is the so-called pretty? Force search algorithm, which assigns the known K colors to N vertices, needs to judge whether it is feasible for all kn cases, so its algorithm complexity is O(kn).

Recently, Malaguti and others put forward a branch and price algorithm [2 1], which is improved on the basis of a genetic algorithm, and the number of graph vertices that can be solved is limited to several hundred. As far as the exact algorithm complexity is concerned, the best result is limited to exponential level. For example, the complexity of k- coloring problem is O(2nn), especially when k = 3 or 4, the complexity of the best algorithms at present is O( 1.3289n) and O( 1.7504n) respectively.