Article ID Journal Published Year Pages File Type
4952204 Theoretical Computer Science 2017 7 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,