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

Algorithm for vertex distinguishing total coloring of random graphs

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数。提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功。实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3)。

A total-coloring is called vertex-distinguishing （VDTC for short） if all the color sets are different. The minimum number of used colors is called the vertex distinguishing total chromatic number. This paper proposed an algorithm that looks for the conflict set, then used some rules to exchange step by step until the value of the objective function meets the requirements, when the coloring was accomplished. The experimental results show that the algorithm can get the vertex distinguishing total chromatic number of random graphs whose vertices number is given effectively,and the time complexity is less than O（n3）.