Study On The Problem Of Several Distinguishing Colorings For Graphs

Graph theory is a new branch of mathematics,and it is widely used.Coloring theory of graphs is an important part of graph theory,and one of the main research topics is the distinguishing colorings problems.In this paper,the problems of the distinguishing colorings of graphs are mainly including in the following aspects:relations of adjacent vertex distinguishing edge chromatic numbers between graphs and its subgraphs,D?2?-vertex-distinguishing total coloring,r-strongly vertex-distinguishing total coloring,D???-vertex-distinguishing edge coloring and adjacent vertex-distinguishing V-total coloring.There are five parts in this paper:In the first part,some related concepts and symbols are mainly introduced.In the second part,the relations of adjacent vertex distinguishing edge chromatic numbers between trees,unicyclic graphs and its subgraphs are completely characterized.It is proved that for a tree T and unicyclic graph G with??G??5 the adjacent vertex distinguishing edge chromatic number of this graphs are no less than its subgraph's.Moreover,some other graphs are constructed such that the adjacent vertex distinguishing edge chromatic number of this graphs less than its subgraph's.In the third part,by Hall's theorem,it is shown that for any graph G,its D?2?-vertex-distinguishing total chromatic number is no more than???G?+1?²+1.Moreover,it is also proved that any tree T??=P₃?,its D?2?-vertex-distinguishing total chromatic number is??T?+1 if any two vertices u and v with maximum degree and d?u,v??3,otherwise,its D?2?-vertex-distinguishing total chromatic number is??T?+2.In the fourth part,it is proved that for any K₃-free graph G with no isolated edges,its 1-strongly vertex-distinguishing total chromatic number is at most 4?²?G?-??G?by analyzing the structure of the graph.Moreover,it is also proved that for any tree T,its2-strongly vertex-distinguishing total chromatic number is not exceeding??T?+3 and its 3-strongly vertex-distinguishing total chromatic number is no more than 3??T?+1.In the fifth part,a smaller upper bound on D???-vertex-distinguishing edge chromatic number and a smaller upper bound on adjacent vertex-distinguishing V-total chromatic number are given respectively by using Lov?asz local lemma in probability method.