Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435563 | Theoretical Computer Science | 2016 | 9 Pages |
Abstract
Let c be a proper total coloring of a graph G=(V,E)G=(V,E) with integers 1,2,…,k1,2,…,k. For any vertex v∈V(G)v∈V(G), let ∑c(v)∑c(v) denote the sum of colors of the edges incident with v and the color of v . If for each edge uv∈E(G)uv∈E(G), ∑c(u)≠∑c(v)∑c(u)≠∑c(v), then such a total coloring is said to be neighbor sum distinguishing. The least k for which such a coloring of G exists is called the neighbor sum distinguishing total chromatic number and denoted by χΣ″(G). Pilśniak and Woźniak conjectured χΣ″(G)≤Δ(G)+3 for any simple graph with maximum degree Δ(G)Δ(G). It is known that this conjecture holds for any planar graph with Δ(G)≥13Δ(G)≥13. In this paper, we prove that for any planar graph, χΣ″(G)≤max{Δ(G)+3,14}.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Cunquan Qu, Guanghui Wang, Jianliang Wu, Xiaowei Yu,