Article ID Journal Published Year Pages File Type
5775508 Applied Mathematics and Computation 2017 13 Pages PDF
Abstract
Given a simple graph G, a proper total-k-coloring ϕ:V(G)∪E(G)→{1,2,…,k} is called neighbor sum distinguishing if Sϕ(u) ≠ Sϕ(v) for any two adjacent vertices u, v ∈ V(G), where Sϕ(u) is the sum of the color of u and the colors of the edges incident with u. It has been conjectured by Pilśniak and Woźniak that Δ(G)+3 colors enable the existence of a neighbor sum distinguishing total coloring. The conjecture is confirmed for any graph with maximum degree at most 3 and for planar graph with maximum degree at least 11. We prove that the conjecture holds for any planar graph G with Δ(G)=10. Moreover, for any planar graph G with Δ(G) ≥ 11, Δ(G)+2 colors guarantee such a total coloring, and the upper bound Δ(G)+2 is tight.
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, , , , ,