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

山东大学学报（理学版） ›› 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)

1262

被引次数

1

摘要： 在图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]. 《山东大学学报(理学版)》, 2026, 61(5): 18-26.
[2] 张鲁宁,王景升. 基于自适应残差动态融合图注意力网络的交通速度预测[J]. 《山东大学学报(理学版)》, 2026, 61(5): 90-101.
[3] 张晓媛, 田毅, 任子涵, 段天宇, 杨斯媛, 张月轩. 拓扑邻域基在密度聚类算法中的应用[J]. 《山东大学学报(理学版)》, 2026, 61(5): 55-64.
[4] 孙歆怡,郑婷婷,孙丽雯. RIME-Transformer模型在复杂时序预测问题中的应用[J]. 《山东大学学报(理学版)》, 2026, 61(5): 79-89.
[5] 白月蓉,魏宗田,王德莉. 基于多火源燃烧连通度的网络抗毁性分析[J]. 《山东大学学报(理学版)》, 2026, 61(4): 102-108.
[6] 王智玄,庞继芳,王智强,宋鹏,李茹. 融合长短期兴趣的属性增强临时群组推荐算法[J]. 《山东大学学报(理学版)》, 2026, 61(3): 54-65.
[7] 杨滨,孙建楠,曹恩国,李子川,周志立. 基于显著性特征的海报设计侵权检测分析[J]. 《山东大学学报(理学版)》, 2026, 61(3): 11-19.
[8] 姚勋祥,刘培培,徐英城,范清兰,包芳勋,张云峰. 基于多重分形优化的图像超分辨率重建[J]. 《山东大学学报(理学版)》, 2026, 61(3): 96-110.
[9] 杨玉,孙圣博,徐子瑞,蒋效伟,宋强,戴红伟. 基于混合变异灰狼优化算法的泊位-岸桥调度[J]. 《山东大学学报(理学版)》, 2026, 61(1): 94-102.
[10] 仲尚,马丽,刘文哲,李雨豪. 融合多尺度注意力机制和改进特征融合的轻量化水面小目标检测模型[J]. 《山东大学学报(理学版)》, 2026, 61(1): 15-25.
[11] 王军涛,黄强. 基于一般重叠函数的模糊数学形态学边缘检测方法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 36-48.
[12] 孙清,叶军,曾广财,宋苏洋,汪一心. 结合蝙蝠算法和紧密度改进的三支K-means算法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 65-75.
[13] 严莉,呼海林,王高洲,张闻彬,潘法定,张啸,郑艳伟. 基于长短时序预测的拓扑构建与控制[J]. 《山东大学学报(理学版)》, 2025, 60(9): 41-51.
[14] 刘福国,刘圆梦,石玉峰,田茂再. 基于VMD-DBO-BiGRU的多因素铁矿石期货价格预测[J]. 《山东大学学报(理学版)》, 2025, 60(9): 121-132.
[15] 刘魏岩,齐迹,梁红,林钰川. 基于混合策略的鹈鹕优化算法[J]. 《山东大学学报(理学版)》, 2025, 60(9): 52-61.
Viewed
Full text


Abstract

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