Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952204 | Theoretical Computer Science | 2017 | 7 Pages |
Abstract
A total k-coloring of G is a mapping Ï:V(G)âªE(G)â{1,â¯,k} such that any two adjacent or incident elements in V(G)âªE(G) receive different colors. Let 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), 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 Lz (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 Lz for each zâ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, which implies that the conjecture proposed by PilÅniak and Woźniak is true for these planar graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jihui Wang, Jiansheng Cai, Baojian Qiu,