图的邻点可区别全染色算法
The algorithm for adjacent-vertex-distinguishing total coloring of graphs

摘要： 在图G的一个正常全染色下,G中任意一点v的色集合是指点v的色以及与v关联的全体边的色所构成的集合.图G的邻点可区别全染色就是图G的正常全染色且使相邻点的色集合不同,其所用最少颜色数称为图G的邻点可区别全色数.设计了一种启发式的邻点可区别全染色算法,该算法根据邻点可区别全染色的约束规则,确定四个子目标函数和一个总目标函数,然后借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功.实验结果表明,该算法可以得到图的邻点可区别全色数,并且算法的时间复杂度不超过O(n3).
Abstract: With a proper total coloring of graph G, for any vertex v, its color set is made up of colors of v ertex vand all its incident edges. An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring, such that any pair of adjacent vertices are incident to distinct sets of colors.The minimum coloring number is called the adjacent-vertex-distinguishing total chromatic number of G. According to adjacent-vertex-distinguishing total coloring rules, this paper presents a heuristic algorithm for the adjacent-vertex-distinguishing total coloring. The algorithm ascertains four sub-functions and one generic function and then iterates gradually in proper sequence with the help of the color matrix and complementary set. When the generic function value equals to zero, we say that the current coloring is successful. The experimental results show that the algorithm can obtain the chromatic number of the adjacent-vertex-distinguishing total coloring of graphs and the time complexity is not more than O(n3)