Article ID Journal Published Year Pages File Type
435563 Theoretical Computer Science 2016 9 Pages PDF
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}.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,