Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5775508 | Applied Mathematics and Computation | 2017 | 13 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Donglei Yang, Lin Sun, Xiaowei Yu, Jianliang Wu, Shan Zhou,