标题:Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz
作者:Qu, Cun-quan; Ding, Lai-hao; Wang, Guang-hui; Yan, Gui-ying
作者机构:[Qu, C.-Q] School of Mathematics, Shandong University, Jinan, 250100, China;[ Ding, L.-H] School of Mathematics, Shandong University, Jinan, 250100, C 更多
通讯作者:Wang, GH(ghwang@sdu.edu.cn)
通讯作者地址:[Wang, GH]Shandong Univ, Sch Math, Jinan 250100, Peoples R China.
来源:应用数学学报(英文版)
出版年:2016
卷:32
期:2
页码:537-548
DOI:10.1007/s10255-016-0583-8
关键词:neighbor sum distinguishing total coloring;Combinatorial Nullstellensatz;neighbor sum distinguishing total choice number
摘要:Let G = (V, E) be a graph and phi : V boolean OR 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 phi is called neighbor sum distinguishing if (f(u) not equal f(v)) for each edge uv is an element of E(G). We say that phi is neighbor set distinguishing or adjacent vertex distinguishing if S(u) not equal S(v) for each edge uv is an element of E(G). For both problems, we have conjectures that such colorings exist for any graph G if k >= Delta (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 Delta(G) and maximum average degree mad(G) has ch(Sigma)''(G) <= Delta(G) + 3 (where ch(Sigma)'' (G) is the neighbor sum distinguishing total choice number of G) if there exists a pair (k, m) is an element of{(6, 4), (5, 18/5), (4, 16/5)} such that Delta(G) >= k and mad (G) < m.
收录类别:CSCD;SCOPUS;SCIE
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84964791127&doi=10.1007%2fs10255-016-0583-8&partnerID=40&md5=f9308e05975b63130d62aac5adde5691
TOP