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

doi:10.1007/s10255-016-0583-8

CSpace > 应用数学研究所

	Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz
	Qu, Cun-quan 1; Ding, Lai-hao 1; Wang, Guang-hui 1; Yan, Gui-ying2
	2016-06-01
发表期刊	ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
ISSN	0168-9673
卷号	32 期号:2 页码:537-548
摘要	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.
关键词	neighbor sum distinguishing total coloring Combinatorial Nullstellensatz neighbor sum distinguishing total choice number
DOI	10.1007/s10255-016-0583-8
语种	英语
资助项目	National Natural Science Foundation of China[11371355] ; National Natural Science Foundation of China[11471193] ; Foundation for Distinguished Young Scholars of Shandong Province[JQ201501] ; Natural Science Foundation of Shandong Province[ZR2013AM001] ; Independent Innovation Foundation of Shandong University[IFYT14012] ; Fundamental Research Funds of Shandong University
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000375233700028
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/22581
专题	应用数学研究所
通讯作者	Wang, Guang-hui
作者单位	1.Shandong Univ, Sch Math, Jinan 250100, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Qu, Cun-quan,Ding, Lai-hao,Wang, Guang-hui,et al. Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz[J]. ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,2016,32(2):537-548.
APA	Qu, Cun-quan,Ding, Lai-hao,Wang, Guang-hui,&Yan, Gui-ying.(2016).Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz.ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,32(2),537-548.
MLA	Qu, Cun-quan,et al."Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz".ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES 32.2(2016):537-548.