The Acyclic Coloring Of Simple Graphs

The graph coloring problem is extended from the map coloring, it is one of the most famous NP─complete problem. The graph coloring theory is used in the mathematical theory, such as mathematical theory and discrete mathematics. With the development of transport and communication network, the graph coloring problem has more and more applications. It can be used to solve specific problems, such as arrange meetings or schedule, chemical storage, and has obtained a very good effect.The acyclic coloring and linear coloring is a generalization of the graph coloring theory. The main research object of the paper is acyclic coloring of several simple graphs. The linear coloring of graphs are also concerned. This paper includes three parts as follows.The first (Chapter 1 and 2 are included) introduces the historical background and fundamental conception of coloring theory. It includes the proper vertex coloring, acyclic coloring, 3-frugal coloring and linear coloring.The second part (Chapter 3 and 4 are included) is the main text. It expores the acyclic and linear coloring.The acyclic coloring is very important for the research of star coloring and 2-distance coloring, it is often used as the lower bound of them. In the research as long as acyclic coloring has progress, the others are improved as well. By analysis the structure of the graph, using mathematical induction,Chapter 3 gives two bounds: acyclic coloring of non-regular graphs of maximum degree five and high degree graphs. In Chapter 4, based on the J. Heuvel lemma, it reduces the upper bound of linear choosability of planar graphs; it gives the more precise upper bound of graphs of maximum degree four and gives a linear time algorithm that achieves this bound, besides, it obtains the optimal upper bound for the linear coloring of d-dimensional grid.The last part summarizes the present paper and give an outlook of the future study in this field.