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

Previous Articles     Next Articles

Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 4

YAO Jing-jing, XU Chang-qing   

  1. School of Science, Heibei University of Technology, Tianjin 300401, China
  • Received:2014-08-07 Revised:2014-11-21 Online:2015-02-20 Published:2015-01-27

Abstract: A proper [k]-total coloring of a graph G is a map φ:VE→{1,2,…,k} such that φ(x)≠φ(y) for each pair of adjacent or incident elements x,yVE. 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 uvE(G), f(u)≠f(v). Let tndiΣ(G) denote the smallest value k in such a coloring of G. Pil?niak and Wo?niak first introduced this coloring and conjectured that tndiΣ(G)≤Δ(G)+3 for any simple graph with maximum degree Δ(G). The maximum average degree of G is the maximum of the average degree of its non-empty subgraphs, which is denoted by mad(G). By using the Combinatorial Nullstellensatz and the discharging method, it is proved that if G is a graph with Δ(G)=3 and mad(G)<125, or Δ(G)=4 and mad(G)<52, then tndiΣ(G)≤Δ(G)+2.

Key words: neighbor sum distinguishing total coloring, maximum average degree, Combinatorial Nullstellensatz

CLC Number: 

  • O157
[1] FLANDRIN E, MARCZYK A, PRZYBYLO J, et al. Neighbor sum distinguishing index[J]. Graphs and Combin, 2013, 29:1329-1336.
[2] 李华龙, 丁来浩, 王光辉. 图的邻和可区别染色[EB/OL]. 中国科技论文在线, 2014, http://www. paper.edu.cn/release-paper/content/20140198. LI Hualong, DING Laihao, WANG Guanghui. Neighbor sum distinguishing colorings of graphs[EB/OL]. Sciencepaper Online, 2014, http://www. paper.edu.cn/releasepaper/content/20140198.
[3] PIL?NIAK M, WO?NIAK M. On the adjacent vertex distinguishing index by sums in total proper colorings[EB/OL]. Graphs and Comb. DOI:10.1007/S00373-013-1339-4(2013).
[4] LI Hualong, LIU Bingqiang, WANG Guanghui. Neighbor sum distinguishing total colorings of K4-minor-free graphs[J]. Frontiers of Mathematics of China, 2013, 8(6):1351-1366.
[5] DONG Aijun, WANG Guanghui. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree[J]. Acta Mathematica Sinica, 2014, 30(4):703-709.
[6] ALON N. Combinatorial Nullstellensatz[J]. Combin Probab Comput, 1999, 8:7-29.
[1] ZHANG Jiang-yue, XU Chang-qing. Linear 2-arboricity of graphs with maximum average degree at most 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 7-10.
[2] PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.
[3] SONG Hong-jie, GONG Xiang-nan, PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing total coloring of Halin graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 65-67.
[4] ZHANG Xin1, XU Lan2, LIU Gui-Zhen1. k-forested coloring of sparse graphs [J]. J4, 2011, 46(4): 1-3.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!