Coloring Of Several Types Of Special Graphs

In 19th-century England,Frederick Guthrie,a student of Augustus de Morgan,and Francis Guthrie(her brother)found that if the areas with common borders are colored by different colors,only 4 colors can be used to complete the entire british map.This gave birth to the famous four-color conjecture,and research on graph coloring theory begins.During the proof of the four-color conjecture,many special graphs are constructed,many proof techniques and graph theory research topics have been produced.Graph coloring theory as an important research direction of graph theory,which has been studied by scholars and experts.Special graphs are used as counterexamples in graph theory research,and serve as extreme graphs that meet some conditions.Therefore,studying the special coloring of special graphs is important in theoretical significance and actual application values.This paper mainly studies the properties of several special graphs(generalized Peterson graph,Sierpinski graph,point split graph)and get their chromatic numbers.In the chapter 1,we introduce the development of graph coloring theory and some special graphs.The research status of Grundy coloring and hued coloring are given.Furthermore,I made a brief introduction for construction and background of the generalized peterson graphs,the generalized Sierpinski graphs,and the point splitting graphs.In the chapter 2,we study the Grundy coloring of the generalized peterson graph.First,some properties of the generalized Peterson graphs are given.The generalized Peterson graphs P(n,l)(n?2l,l?1)are 3 regular graphs according to their structures.We give the specific coloring method and get its grundy number.In the chapter 3,we study the chromatic coloring of some special graphs.First,we study some properties of the square graphs of trees with maximum degree 3.The plane map of the square graph of the tree with maximum degree 3 is obtained and the concrete construction method is given.It is also proved that it is a perfect graph.Then we consider the coloring and abnormal coloring of generalized Sierpinski graph and friendship graph,and obtain their specific chromatic numbers.In the chapter 4,we study grundy coloring of point splitting graphs of path,circle,wheel and fan.The structure of point splitting graphs is a method to transform a graph,which is often used in the study of graph theory.By analyzing the structure of special graphs,the coloring methods and coloring numbers are given.In this paper,the chromatic number of the graph is obtained by constructing specific color-ings,and the rationality of the construction is proved by theoretical analysis.These results reflect the value of special graph coloring theory.At the same time,we also put forward some problems that can be further studied in some chapters.