Research On Adjacent Vertex-distinguishing Coloring Problems For Two Classes Of Graphs

This thesis introduces the concepts of adjacent vertex-distinguishing proper edgecoloring, adjacent vertex-distinguishing total coloring and k-th power graphs, and wedefne one kind of two dimensional generalized grid graphs H2(G, n, m; k1, k2), takingthis kind of graphs as the main object of research. This thesis consists of four chapters.The frst chapter of this thesis is introduction, which includes the research back-ground of graph theory, and some preliminaries which are incident to this thesis.In the second chapter, the adjacent vertex-distinguishing proper edge chromaticnumbers of two dimensional generalized grid graph H2(Cl, n, m; l, l) generated by thecycle Cl, two dimensional generalized grid graph H2(K4, n, m;4,4) generated by thecomplete graph K4and two dimensional generalized grid graph H2(Kp,p, n, m; p, p)generated by the complete bipartite graph Kp,pare given by using the method ofcoloring constructing, and the adjacent vertex-distinguishing edge chromatic numberconjecture is also verifed.In the third chapter, according to the structure of the graphs, the adjacent vertex-distinguishing total chromatic numbers of two dimensional generalized grid graphH2(C5, n, m;5,5) generated by the cycle C5is given by using the method of coloringconstructing, and the adjacent vertex-distinguishing total chromatic number conjec-ture is also verifed.In the fourth chapter, the adjacent vertex-distinguishing total coloring of somepower graphs are discussed, and the adjacent vertex-distinguishing total chromaticnumbers of some power graphs, such as the C3kk23n, C43n, Wn, Fn, Snand Sn,nare givenby using the method of coloring constructing, and the adjacent vertex-distinguishingtotal chromatic number conjecture is also verifed.