中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 应用数学研究所
Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz

文献类型：期刊论文

作者Qu, Cun-quan1; Ding, Lai-hao1; Wang, Guang-hui1; Yan, Gui-ying2
刊名ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
出版日期2016-06-01
卷号32期号:2页码:537-548
关键词neighbor sum distinguishing total coloring Combinatorial Nullstellensatz neighbor sum distinguishing total choice number
ISSN号0168-9673
DOI10.1007/s10255-016-0583-8
英文摘要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.
资助项目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记录号WOS:000375233700028
出版者SPRINGER HEIDELBERG
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/22580]  
专题应用数学研究所
通讯作者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.

入库方式： OAI收割

来源：数学与系统科学研究院

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。