CSpace  > 应用数学研究所
Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz
Qu, Cun-quan1; Ding, Lai-hao1; Wang, Guang-hui1; Yan, Gui-ying2
2016-06-01
Source PublicationACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
ISSN0168-9673
Volume32Issue:2Pages:537-548
AbstractLet 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.
Keywordneighbor sum distinguishing total coloring Combinatorial Nullstellensatz neighbor sum distinguishing total choice number
DOI10.1007/s10255-016-0583-8
Language英语
Funding ProjectNational 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 Research AreaMathematics
WOS SubjectMathematics, Applied
WOS IDWOS:000375233700028
PublisherSPRINGER HEIDELBERG
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/22581
Collection应用数学研究所
Corresponding AuthorWang, Guang-hui
Affiliation1.Shandong Univ, Sch Math, Jinan 250100, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Qu, Cun-quan]'s Articles
[Ding, Lai-hao]'s Articles
[Wang, Guang-hui]'s Articles
Baidu academic
Similar articles in Baidu academic
[Qu, Cun-quan]'s Articles
[Ding, Lai-hao]'s Articles
[Wang, Guang-hui]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Qu, Cun-quan]'s Articles
[Ding, Lai-hao]'s Articles
[Wang, Guang-hui]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.