Study On The Problem Of Adjacent Vertex-Distinguishing Total Coloring Of Graphs

The coloring problem of graphs is induced by computer science, which has widely application in networks. The adjacent vertex-distinguishing total coloring is the proper total coloring which demands the adjacent vertices with different color sets. The notion of adjacent vertex- distinguishing total coloring was introduced firstly by professor Zhang Zhongfu et al in 2004, and the authors conjectured that x_at(G) ≤ △(G) + 3.In this master thesis, we mainly discuss the adjacent vertex- distinguishing total chromatic numbers of some special graphs and prove that Zhang's conjecture holds for these graphs. Then we get the adjacent vertex-distinguishing total chromatic numbers of the Halin Graphs. Moreover, we investigate the Generalized Petersen Graphs, prove that some classes of positive integers can't structure the Generalized Petersen Graphs and get the result that the adjacent vertex-distinguishing total chromatic number is 5. Finally, based on the number and the parity of circles contained by the graph, we get the adjacent vertex-distinguishing total chromatic number of two classes of graphs.