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)

838

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] YE Xiao-ming, CHEN Xing-shu, YANG Li, WANG Wen-xian, ZHU Yi, SHAO Guo-lin, LIANG Gang. Anomaly detection model of host group based on graph-evolution events [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 1-11.
[2] . Equilibrium decisions of a two-layer supply chain network considering retailers horizontal fairness [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 69-82.
[3] . Vertex-distinguishing IE-total coloring and general-total coloring of K1,3,p and K1,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 53-60.
[4] LIU Xiao-hua, MA Hai-cheng. Order of matching energy and Hosoya index of Q-shape graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 61-65.
[5] XU Li-dong, WANG Ming-qiang. A meet-in-the-middle attack on 10-round AES-128 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 39-45.
[6] CUI Zhao-yang, SUN Jia-qi, XU Song-yan, JIANG Xin. A secure clustering algorithm of Ad Hoc network for colony UAVs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 51-59.
[7] GAO Rui-mei, CHU Ying. Freeness of arrangements between the Weyl arrangements of types An-1 and Bn [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 70-75.
[8] HE Xin-hua, WAN Fan, HU Wen-fa, ZHENG Ai-bing. Emergency supply scheduling optimization under stochastic simulation of complex risk variables [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(5): 1-11.
[9] . Interval algorithm for mixed integer nonlinear two-level programming problems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(2): 9-17.
[10] LI Mei-lian, DENG Qing-ying. Maple calculation of the transition polynomial of plane graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 27-34.
[11] FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35-41.
[12] ZHU Dan, XIE Xiao-yao, XU Yang, XIA Meng-ting. Evaluation method for network security level based on cloud model and Bayesian feedback [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 53-62.
[13] KANG Hai-yan, HUANG Yu-xuan, CHEN Chu-qiao. Enhancing privacy for geographic information based on video analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 19-29.
[14] . Graph model based trustworthy resource scheduling algorithm in cloud environment [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 63-74.
[15] DAI Hong-xiu, WANG Nan, AIMAIER·Aikebaijiang, LIN Meng. Preparation of the GO/PPy/Pb3O4 modified electrode for electrochemical sensing application [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(9): 98-102.
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