您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (02): 14-21.doi: 10.6040/j.issn.1671-9352.0.2014.145

• 论文 • 上一篇    下一篇

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

李敬文, 贾西贝, 董威, 李小慧, 闫光辉   

  1. 兰州交通大学电子与信息工程学院, 甘肃 兰州 730070
  • 收稿日期:2014-04-10 修回日期:2014-10-14 出版日期:2015-02-20 发布日期:2015-01-27
  • 作者简介:李敬文(1965-),男,教授,研究方向为图论算法及其应用. E-mail:lijingwen28@163.com
  • 基金资助:
    国家自然科学基金资助项目(11461038,61163010,61163037);预研基金(JCYY2013012)

The algorithm for adjacent-vertex-distinguishing total coloring of graphs

LI Jing-wen, JIA Xi-bei, DONG Wei, LI Xiao-hui, YAN Guang-hui   

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Received:2014-04-10 Revised:2014-10-14 Online:2015-02-20 Published:2015-01-27

PDF (PC)

787

摘要： 在图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).

Key words: adjacent-vertex-distinguishing total chromatic number, adjacent-vertex-distinguishing total coloring, graph, algorithm

中图分类号: 

  • TP301
[1] VIZING V G. On an estimate of the chromatic class of a p-graph[J]. Discret Analiz, 1964, 3:25-30.
[2] BEHZAD M. Graphs and their chromatic numbers[D]. Michigan: Michigan State University, 1965.
[3] BURRIS A C, SCHELP R H. Vertex-distinguishing proper edge-coloring[J]. Graph Theory, 1997, 26(2):70-82.
[4] BALISTER P N, RIORDAN M, SCHELP R H. Vertex-distinguishing proper edge-colorings[J].Graph Theory, 2003, 42(2):95-109.
[5] ZHANG Zhongfu, LIU Linzhong, WANG Jianfang. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15(3):623-626.
[6] ZHANG Zhongfu, CHEN Xiangen, LI Jingwen, et al. On adjacent vertex distinguishing total coloring of graphs[J].Sci China: Ser A, 2005, 48(3):289-299.
[7] ZHANG Zhongfu, QIU Pengxiang, XU Baogen, et al. Vertex distinguishing total coloring of graphs[J]. Ars Combinatoria, 2008, 87(2):33-45.
[8] CHE N Xiangen. On the adjacent vertex-distinguishing total coloring number of graphs with Δ=3[J]. Discrete mathematics, 2008, 308(17):4003-4007.
[9] Jonathan Hulgan. Concise proofs for adjacent vertex-distinguishing total colorings[J]. Discrete Mathematics, 2009, 309(8):2548-2550.
[10] Hervé Hocquard, Mickaël Montassier. Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five[J]. Electronic Notes in Dis Math, 2011, 38:457-462.
[11] HUANG Danjun, WANG Weifan, YAN Chengchao. A note on the adjacent vertex distinguishing total chromatic number of graphs[J]. Dis Math, 2012, 312(24):3544-3546.
[12] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: The Macmillan Press Ltd, 1976.
[13] 文丽,吴良大. 高等数学[M]. 北京:北京大学出版社,1999. WEN Li, WU Liangda. Advanced maths[M]. Beijing: Peking University Press, 1999.
[1] 叶晓鸣,陈兴蜀,杨力,王文贤,朱毅,邵国林,梁刚. 基于图演化事件的主机群异常检测模型[J]. 山东大学学报（理学版）, 2018, 53(9): 1-11.
[2] 寇艳芳,陈祥恩,王治文. K1,3,p和 K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报（理学版）, 2018, 53(8): 53-60.
[3] 刘小花,马海成. Q形图的匹配能序及Hosoya指标排序[J]. 山东大学学报（理学版）, 2018, 53(8): 61-65.
[4] 许力冬,王明强. 对10轮AES-128的中间相遇攻击[J]. 山东大学学报（理学版）, 2018, 53(7): 39-45.
[5] 刘华,叶勇,魏玉梅,杨鹏,马明,冶建华,马娅磊. 一类离散宿主-寄生物模型动态研究[J]. 山东大学学报（理学版）, 2018, 53(7): 30-38.
[6] 崔朝阳,孙甲琦,徐松艳,蒋鑫. 适用于集群无人机的自组网安全分簇算法[J]. 山东大学学报（理学版）, 2018, 53(7): 51-59.
[7] 高瑞梅,初颖. Weyl构形An-1和Bn之间的构形的自由性[J]. 山东大学学报（理学版）, 2018, 53(6): 70-75.
[8] 何新华,万帆,胡文发,郑爱兵. 复杂风险变量随机模拟下的应急供应调度[J]. 山东大学学报（理学版）, 2018, 53(5): 1-11.
[9] 宋省身,杨岳湘,江宇. 基于单指令级并行的快速求交算法[J]. 山东大学学报（理学版）, 2018, 53(3): 54-62.
[10] 朱林. A4型箭图的可分单态射表示和RSS等价[J]. 山东大学学报（理学版）, 2018, 53(2): 1-8.
[11] 刘园园,曹德欣,秦军. 非线性二层混合整数规划问题的区间算法[J]. 山东大学学报（理学版）, 2018, 53(2): 9-17.
[12] 李美莲,邓青英. 平图的transition多项式的Maple计算[J]. 山东大学学报（理学版）, 2018, 53(10): 27-34.
[13] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[14] 齐平, 王福成, 王必晴. 一种基于图模型的可信云资源调度算法[J]. 山东大学学报（理学版）, 2018, 53(1): 63-74.
[15] 孙泽锐,王继军,李国祥,夏国恩. 基于插值图像的可逆信息隐藏算法[J]. 山东大学学报（理学版）, 2018, 53(1): 46-52.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发