Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles

详细信息    查看全文

• 作者：Jihui Wang^a ; ^{wangjh@ujn.edu.cn} ; Jiansheng Cai^b ; Baojian Qiu^a
• 关键词：Neighbor sum distinguishing total coloring ; Choosability ; Combinatorial Nullstellensatz ; Planar graph
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：24 January 2017
• 年：2017
• 卷：661
• 期：Complete
• 页码：1-7
• 全文大小：264 K
• 卷排序：661

文摘

A total k-coloring of G   is a mapping ϕ:V(G)∪E(G)→{1,⋯,k}ϕ:V(G)∪E(G)→{1,⋯,k} such that any two adjacent or incident elements in V(G)∪E(G)V(G)∪E(G) receive different colors. Let f(v)f(v) denote the sum of colors of the edges incident to v and the color of v. A k-neighbor sum distinguishing total coloring of G is a total k-coloring of G   such that for each edge uv∈E(G)uv∈E(G), f(u)≠f(v)f(u)≠f(v). By χ∑″(G), we denote the smallest value k in such a coloring of G  . Pilśniak and Woźniak first introduced this coloring and conjectured that χ∑″(G)≤Δ(G)+3 for any simple graph G  . Let LzLz(z∈V∪E)(z∈V∪E) be a set of lists of integer numbers, each of size k. The smallest k   for which for any specified collection of such lists, there exists a neighbor sum distinguishing total coloring using colors from LzLz for each z∈V∪Ez∈V∪E is called the neighbor sum distinguishing total choosability of G  , and denoted by ch∑″(G). In this paper, we prove that ch∑″(G)≤Δ(G)+3 for planar graphs without adjacent triangles with Δ(G)≥8Δ(G)≥8, which implies that the conjecture proposed by Pilśniak and Woźniak is true for these planar graphs.