Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz

被引:5
作者
Cun-quan QU [1 ]
Lai-hao DING [1 ]
Guang-hui WANG [1 ]
Gui-ying YAN [2 ]
机构
[1] School of Mathematics, Shandong University
[2] Academy of Mathematics and Systems Science, Chinese Academy of Sciences
基金
中国国家自然科学基金;
关键词
neighbor sum distinguishing total coloring; Combinatorial Nullstellensatz; neighbor sum distinguishing total choice number;
D O I
暂无
中图分类号
O157.5 [图论];
学科分类号
070104 ;
摘要
Let G =(V,E) be a graph and φ:V∪E→ {1,2,…,k} be a total-k-coloring of G.Let f(v)(S(v))denote the sum(set) of the color of vertex v and the colors of the edges incident with v.The total coloring φis called neighbor sum distinguishing if(f(u)≠f(v)) for each edge uv ∈ E(G).We say that φ is neighbor set distinguishing or adjacent vertex distinguishing if S(u)≠ S(v) for each edge uv ∈ E(G).For both problems,we have conjectures that such colorings exist for any graph G if k ≥△(G) + 3.The maximum average degree of G is the maximum of the average degree of its non-empty subgraphs,which is denoted by mad(G).In this paper,by using the Combinatorial Nullstellensatz and the discharging method,we prove that these two conjectures hold for sparse graphs in their list versions.More precisely,we prove that every graph G with maximum degree △(G) and maximum average degree mad(G) has ch;"(G) ≤△(G) + 3(where ch;"(G) is the neighbor sum distinguishing total choice number of G) if there exists a pair(k,m) ∈ {(6,4),(5,18/5),(4,16/5)}such that △(G) ≥ k and mad(G) < m.neighbor sum distinguishing total choice number of G) if there exists a pair(k,m) ∈ {(6,4),(5,18/5),(4,16/5)}such that △(G)≥k and mad(G) < m.
引用
收藏
页码:537 / 548
页数:12
相关论文
共 14 条
[1]  
Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz [J]. DING LaiHao,WANG GuangHui,YAN GuiYing.&nbsp&nbspScience China(Mathematics). 2014(09)
[2]  
Neighbor Sum Distinguishing Total Colorings of Graphs with Bounded Maximum Average Degree [J]. Ai Jun DONG,Guang Hui WANG.&nbsp&nbspActa Mathematica Sinica(English Series). 2014(04)
[3]   高度平面图的邻点可区别全染色 [J].
黄丹君 ;
王维凡 .
中国科学:数学, 2012, 42 (02) :151-164
[4]  
On adjacent-vertex-distinguishing total coloring of graphs [J]. ZHANG Zhongfu, CHEN Xiang’en, LI Jingwen, YAO Bing, LU Xinzhong & WANG Jianfang College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China;Department of Computer, Lanzhou Normal College, Lanzhou 730070, China;Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, China;College of Information and Electrical Engineering, Lanzhou Jiaotong University, Lanz
[5]   The adjacent vertex distinguishing total coloring of planar graphs [J].
Wang, Weifan ;
Huang, Danjun .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 27 (02) :379-396
[6]   Neighbor sum distinguishing total colorings of K 4-minor free graphs [J].
Li, Hualong ;
Liu, Bingqiang ;
Wang, Guanghui .
FRONTIERS OF MATHEMATICS IN CHINA, 2013, 8 (06) :1351-1366
[7]  
Weighted-1-antimagic graphs of prime power order [J] . Po-Yi Huang,Tsai-Lien Wong,Xuding Zhu.&nbsp&nbspDiscrete Mathematics . 2011 (14)
[8]  
Antimagic labelling of vertex weighted graphs [J] . Tsai‐Lien Wong,Xuding Zhu.&nbsp&nbspJ. Graph Theory . 2011 (3)
[9]   Total Weight Choosability of Graphs [J].
Wong, Tsai-Lien ;
Zhu, Xuding .
JOURNAL OF GRAPH THEORY, 2011, 66 (03) :198-212
[10]   Adjacent vertex distinguishing total colorings of outerplanar graphs [J].
Wang, Yiqiao ;
Wang, Weifan .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 19 (02) :123-133