JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (02): 14-21.doi: 10.6040/j.issn.1671-9352.0.2014.145

Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] TANG Buzhou, HU Han. Construction of technology and application of knowledge graph in power safety [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(5): 18-26.
[2] ZHANG Luning, WANG Jingsheng. Traffic speed prediction study based on adaptive residual dynamic fusion graph attention network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(5): 90-101.
[3] ZHANG Xiaoyuan, TIAN Yi, REN Zihan, DUAN Tianyu, YANG Siyuan, ZHANG Yuexuan. Application of topology neighborhood bases in density clustering algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(5): 55-64.
[4] SUN Xinyi, ZHENG Tingting, SUN Liwen. Application of RIME-Transformer model in complex time series prediction problems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(5): 79-89.
[5] BAI Yuerong, WEI Zongtian, WANG Deli. Analysis of network invulnerability based on the multi-fire source burning connectivity [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(4): 102-108.
[6] WANG Zhixuan, PANG Jifang, WANG Zhiqiang, SONG Peng, LI Ru. Attribute enhanced temporary group recommendation algorithm fusing long-and short-term interests [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(3): 54-65.
[7] YANG Yu, SUN Shengbo, XU Zirui, JIANG Xiaowei, SONG Qiang, DAI Hongwei. Hybrid mutation based gray wolf optimization algorithm for berth-quay crane scheduling [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(1): 94-102.
[8] SUN Qing, YE Jun, ZENG Guangcai, SONG Suyang, WANG Yixin. Three-way K-means algorithm combining the bat algorithm and the improved compactness [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(1): 65-75.
[9] YAN Li, HU Hailin, WANG Gaozhou, ZHANG Wenbin, PAN Fading, ZHANG Xiao, ZHENG Yanwei. Topology construction and control based on long short-term prediction [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(9): 41-51.
[10] LIU Fuguo, LIU Yuanmeng, SHI Yufeng, TIAN Maozai. Multi-factor iron ore futures price prediction based on VMD-DBO-BiGRU [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(9): 121-132.
[11] LIU Weiyan, QI Ji, LIANG Hong, LIN Yuchuan. A pelican optimization algorithm based on hybrid strategy [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(9): 52-61.
[12] WANG Jiang, LI Jingwen, GAO Xin, SUN Liangjing. Adjacent vertex reducible total labeling of some joint graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(8): 57-67.
[13] WANG Hui, LIU Mengmeng. Lower bound of Mostar index with respect to tricyclic graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(8): 68-77.
[14] WU Xiaojun, CHEN Yidan, HAO Yaojun, SONG Changwei, HE Deqing. Multi-label feature selection with label manifold and dynamic graph constraints [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(7): 69-83.
[15] WU Xinyao, XU Ji. Hierarchical graph representation learning based on graphical mutual information pooling [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(7): 84-93.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd