Two New Algorithms For The Proper 4-Coloring Of Planar Graphs

The coloring of planar graphs plays an important role in graph theory and Combinatorial Optimization theory. It has wide applications in the realm of other sciences. The origin of the coloring of planar graphs is four color conjecture(i.e., any map can be colored using four colors in such a way that adjacent regions receive different colors). Although the four color conjecture was proved in 1976 by K.Appel, W.Haken and J.Koch by using a computer, there is only a theorical result, it does not provide a practical coloring algorithm for planar graph. Hence, Finding efficient coloring algorithms for planar graphs, especially, constructing an algorithm for the proper 4-coloring of planar graphs, becomes a hot subject in the graph theory. But the complexity of the problem itself decides that it is very difficult.In this paper, we first introduce the development of planar graph coloring theory and some new results, then deeply discuss the properties of boolean representation for 4-coloring of planar graphs which was first proposed by Ulji, and present two new 4-coloring algorithms for maximal planar graphs. The details are as follows:1. In Chapter 3, we provide a proper 4-coloring algorithm for maximal planar graphs, the algorithm can find all proper 4-coloring solutions for any given maximal planar graph. Different from the algorithms in the literature, it has following advantages: it can obtains all solution of the problem, and the algorithm is more efficient since there is no trial and error step in the algorithm. Certainly, the complexity of the algorithm is exponential time.2. In Chapter 4, in order to overcome the fault as above mentioned, we construct another new algorithm for maximal planar graphs. The algorithm can rapidly obtain a solution of the problems. The execution time complexity of this algorithm is O(e), where e represents the number of edges in any given maximal planar graphs.