随机图的点可区别V-全染色算法

Algorithm for vertex distinguishing V-total coloring of graphs

图G的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图G的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过O(n3)。

For vertex distinguishing V-total coloring of graph G,the colors of both adjacent edges and vertex with its incident edges should be different.Moreover,the color sets of any vertices are not the same.The minimum coloring number is called the vertex-distinguishing V-total chromatic number of G.This paper presents a heuristic algorithm for vertex distinguishing V-total coloring according to its constrain rules.The algorithm iterates gradually in proper sequence with the help of the color matrix and complementary set.When the generic function value meets the requirement,we say that the current coloring is successful.This paper gives a detail description of the algorithm,algorithm analysis and algorithm testing results,and also verifies the vertex distinguishing V-total coloring conjecture of graphs with given points.The experimental results show that the algorithm has good efficiency and can obtain the vertex distinguishing V-total chromatic number of graphs,and the time complexity of the algorithm is not more than O（n3）.