JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2016, Vol. 51 ›› Issue (4): 65-67.doi: 10.6040/j.issn.1671-9352.0.2015.300

Previous Articles     Next Articles

Neighbor sum distinguishing total coloring of Halin graph

SONG Hong-jie, GONG Xiang-nan, PAN Wen-hua, XU Chang-qing*   

  1. School of Science, Heibei University of Technology, Tianjin 300401, China
  • Received:2015-06-23 Online:2016-04-20 Published:2016-04-08

Abstract: Let [k]={1,2,…,k}, a mapping φ is a proper [k]-total coloring of a graph G. Let f(v) denote the sum of the color of vertex v and the colors of the edges incident with v. A [k]-neighbor sum distinguishing total coloring of G is a [k]-total coloring of G such that for each edge uv∈E(G), f(u)≠f(v). Let χ″Σ(G) denote the smallest value k in such a coloring of G. Pilsniak and Wozniak conjectured that χ″Σ(G)≤Δ(G)+3 for any simple graph with maximum degree Δ(G). By using the Combinatorial Nullstellensatz, it shows that the conjecture holds for any Halin graph.

Key words: Halin graph, combinatorial nullstellensatz, neighbor sum distinguishing total coloring

CLC Number: 

  • O157
[1] PILSNIAK M, WOZNIAK M. On the adjacent vertex distinguishing index by sums in total proper colorings[EB/OL]. Preprint MD 051, http://www.ii.uj.edu.pl/preMD/index, php.
[2] 姚京京, 徐常青. 最大度为3或4的图的邻和可区别全染色[J]. 山东大学学报(理学版), 2015, 50(2):9-13. YAO Jingjing, XU Changqing. Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 4[J]. Journal of Shandong University(Natural Science), 2015, 50(2):9-13.
[3] LI Hua-long, LIU Bing-qiang, WANG Guang-hui. Neighbour sum distinguishing total colorings of K4-minor-free graphs[J]. Frontiers of Mathematics in China, 2013, 8(6):1351-1366.
[4] LI Hua-long, DING Lai-hao, LIU Bing-qiang, et al. Neighbour sum distinguishing total coloring of planner graphs[J/OL]. Journal of Combinatorial Optimization, 2013, doi: 10.1007/s10878-013-9660-6.
[5] DONG Ai-jun, WANG Guang-hui. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree[J]. Acta Mathematica Sinica, English Series, 2014, 30(4):703-709.
[6] WANG Ji-hui, MA Qiao-ling, HAN Xue. Neighbor sum distinguishing total colorings of triangle free planar graphs[J]. Acta Mathematica Sinica, English Series, 2015, 31(2): 216-224.
[7] YAO Jing-jing, SHAO Ze-ling, XU Chang-qing. Neighbor sum distinguishing total choosabiliby of graphs with Δ=3[J/OL]. Advances In Mathematics(China), 2014, doi: 10.11845/sxjz.2014195b.
[8] BONDY J, MURTY U. Graph theory[M]. London: Springer, 2008.
[9] 姚京京, 孔海荣, 徐常青. Halin图的邻和可区别边染色与边权点染色[J]. 数学的实践与认识, 2015, 45(4):294-298. YAO Jingjing, KONG Hairong, XU Changqing. Neighbor sum distinguishing edge coloring and vertex coloring edge weighting of Halin graph[J]. Mathematics in Practice and Theory, 2015, 45(4):294-298.
[10] ALON N. Combinatorial nullstellensatz[J]. Combin Probab Comput, 1999, 8:7-29.
[1] MENG Xian-yong, GUO Jian-hua, SU Ben-tang. The complete coloring of 3-regular Halin graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(12): 127-129.
[2] YAO Jing-jing, XU Chang-qing. Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 9-13.
[3] YAO Ming1, YAO Bing2*, CHEN Xiang-en2. On complete chromatic numbers of cubic Halin graphs [J]. J4, 2012, 47(2): 65-70.
[4] SHAN Wei1, WU Jian-liang2. Double edge coloring on two classes of approximate Halin graphs [J]. J4, 2010, 45(10): 27-30.
[5] MA Qiao-ling,SHAN Wei and WU Jian-liang . Edge coloring with restriction of vertices and faces on Halin graphs [J]. J4, 2007, 42(4): 24-27 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!