完全图的点可区别全染色算法

徐晓青 李双元 张卫平

摘要：设f是图G的一个正常的k-全染色，若G中任意两点的色集不同，则称f为G的k-点可区别全染色，简记为k-VDTC of G,，并称最小的k为G的点可区别全色数。该文针对完全图的点可区别全染色的特点提出了分类顺次着色算法，该算法首先按照一定的规则对元素进行分类然后对元素进行顺次着色，同时给出关联锁表，根据关联锁表判断是否得到问题的解。实验结果表明：该算法有效地解决了完全图的点可区别全染色问题。

关键词：k-点可区别全染色；点可区别全色数；分类顺次着色；完全图；关联锁表

中图分类号：TP18文献标识码：A文章编号：1009-3044(2012)18-4498-03

Algorithm for the Vertex-Distinguishing Total Coloring of Complete Graphs

XU Xiao-qing, LI Shuang-yuan, ZHANG Wei-ping

(Lanzhou Jiaotong University,Lanzhou 730070,China)

Abstract: Let f be a proper k- total coloring of a graph G , if for any two distinct vertices u and v in G,the set of colors of u differs from the set of colors of v, f is called a k-vertex distinguishing total coloring of G , is abbreviated k-VDTC of G and the minimal number k of colors required for vertex-distinguishing total coloring of G is called the vertex-distingishing total chromatic number of G.In this paper, a new algorithm whose name is algorithm of classified order coloring is proposed on the base of the characteristics of the vertex-distinguish? ing total coloring of complete graphs .All of its elements are classified according to some rules and then are colored in proper sequence in the algorithm. Moreover, a relatelocktable is presented to judge whether the result is correct. The experimental results show that the algo? rithm can effectively solve the vertex-distinguishing total coloring of complete graphs.

Key words: vertex-distinguishing total coloring; vertex-distinguishing total chromatic number; classified order coloring; relatelocktable

该文根据完全图的点可区别全染色的特点，设计了聚类顺次着色的算法，利用关联锁表和元素的2次幂求和对算法进行控制，使得算法有效的解决了完全图的点可区别全染色。

[1] ZHANG Zhong-fu, QIU Peng-xiang, XU Bao-gen, et al. vertex-distinguishing toal coloring of graphs[J]. Ars Com, 2008, 87:33-45.

[2] BURRIS A C, SCHELP R H. Vertex-distinguishing proper edge-colorings[J]. Journal of Graph Theory, 1997, 26(2): 73-82.

[3] BALISTER P N, GYORI E,LEHEL J, et al. Adjacent vertex distinguish edge-colorings[J]. Journal on Discrete Mathematics, 2007, 21(1): 237-250.

[4] HATAMI H.Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]. Journal of Combinatorial Theory(Series B), 2005, 95(2): 246-256.

[5] ZHONG Zhong-fu, LIU Lin-zhong, WANG Jian-fang. Adjacent strong edge coloring of graphs[J]. Appl Math Lett, 2002, 15(5): 623-626.

[6]张忠辅,李敬文,陈祥恩，等.图的距离不大于β的任意两点可区别边染色[J].中国科学,2006,49(3): 703-708.

[7]张忠辅,李敬文,陈祥恩,等.图的距离不大于β的任意两点可区别全染色[J].中国科学,2006,49（10): 1430-1440.

[8] BONDY J A, MARTY U S R. Graph theory with application[M]. New York:The Macmillan Press Ltd, 1976.

[9] ZHANG Zhong-fu, CHEN Xiang-en, LI Jing-wen,et al. On adjacent-vertex-distinguishing total coloring of graphs[J]. Sci China(Ser A), 2005, 48(3):289-299.