The Research Of Algorithms For Some Distinguishing Not Necessarily Colorings Of Graph

This dissertation is devoted to studying the distinguishing not necessarily coloring problems of graph. Graph coloring is a very important direction in the study of graph theory,as its good application background.Many problems can be solved with the help of graph coloring,such as timetabling problem,assignment problem and integrated circuit wiring.It can be said that the research of graph coloring can provide a new method for resolving practical problems.Since the complexity of the practical problems,the proper vertex coloring or edge coloring can not entirely meet the requirements,then kinds of coloring problems which contain(adjacent) vertex distinguishing coloring,uniform coloring, reducible coloring,have been proposed.And the distinguishing not necessarily coloring in this paper is a weakening of proper distinguishing coloring. Since the graph coloring problem is a NP- complete problem,the algorithms to solve the problem mainly depends on the intelligent algorithms which are only limited to solve the vertex coloring or edge coloring for special graphs,can’t solve the total coloring or distinguishing coloring problem.However the graphs which are transformed form practical problems all have a certain randomness,so,it is very important to search for efficiency algorithms for arbitrary graphs.For adjacent vertex distinguishing not necessarily coloring problem,although some theoretical results are involved in published literatures,there is not any feasible algorithms to be found. Therefore,the implementation of the algorithm has high practical significance on the research of issues related. In this paper,new algorithms for arbitrary simple connected graphs are designed based on the coloring requirements.The test results show that the algorithms have good efficiency.The main research work is as follows:(1)Introduce some basic concepts and conjectures of the colorings,and give a survey of the research background,the domestic and foreign research trends.(2)The basic idea of some classical intelligent optimization algorithms are introduced,including their application in graph coloring and analysis their performance on solving graph coloring problems at last.(3)For adjacent vertex distinguishing not necessarily coloring of simple connected graphs,this dissertation design four algorithms.One of them is based on proper vertex coloring named adjacent vertex distinguishing E-total coloring. The other is adjacent vertex distinguishing V-total coloring,adjacent vertex distinguishing I-total coloring and adjacent vertex distinguishing VI-total coloring which are based on proper edge coloring. The former is to color the vertices firstly and then to color edges,while the latter uses the opposite direction. In addition,the edge coloring method designed among the algorithms can be applied to other total colorings or distinguishing total colorings. Detailed process and test are alsogiven in this paper,and the correctness,the convergence and the time complexity is analyzed.Finally,a summary of the algorithms is made.