The3-Coloring And Linear Coloring Of Planar Graphs

The graph coloring problem is derived from the famous “Four Color Conjecture”.It is an important branch of graph theory. The graph coloring theory is applied to notonly mathematical theory, such as discrete mathematics and combinatorial analysis, butalso many other fields, such as optimization, traffic and transportation, communicationnetwork, computer theory and so on. It can help us to solve the problem of arrangingmeeting or exam schedule. It can also be used to solve the problem of chemicals storage.Because of the graph coloring theory is theoretically and practically important in manyfields, it is always one of the hot topics of graph theory.In this paper, we mainly study the3-coloring and linear coloring of planar graphs.They are all vertex coloring. The linear coloring is based on the proper vertex coloring.And the3-coloring means a proper vertex coloring with three colors. The main contentsof this paper can be divided into four parts.The first part (Chapter1) mainly introduces the historical background of the graphcoloring problem, the study purpose and the main contents of this paper.The second part (Chapter2) introduces the related basic concepts, especially theproper vertex coloring and the linear coloring. Besides, this part summarizes the currentresearch on the3-coloring and the linear coloring of graphs.The third part (Chapter3and Chapter4) is the core of this paper. The mainresearch findings are included in this part. We mainly explore the3-coloring and thelinear coloring of planar graphs in this part. Chapter3first gives a lemma to state theconfiguration of the minimum graph which can not be3-colorable. Then it gives threesufficient conditions for planar graphs to be3-colorable. Chapter4gives two theoremsand two corollaries on linear coloring of planar graphs. To some extent, the upper boundof the linear chromatic number of planar graphs was reduced.The fourth part (Chapter5) summarizes the main results in this paper, points outthe innovative points, and gives an outlook of the future study in this field.