کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435184 | 689877 | 2016 | 5 صفحه PDF | دانلود رایگان |
• We improve the known results and get that χΣ″(G)≤max{Δ(G)+2,14}.
• The bound Δ(G)+2Δ(G)+2 is sharp.
• The proof uses the Combinatorial Nullstellensatz, color-changing and discharging method.
Let G=(V(G),E(G))G=(V(G),E(G)) be a graph and ϕ be a proper total k-coloring of G . Let f(v)f(v) denote the sum of the color on a vertex v and colors on all the edges incident with v. ϕ is neighbor sum distinguishing if f(u)≠f(v)f(u)≠f(v) for each edge uv∈E(G)uv∈E(G). The smallest integer k for which such a coloring of G exists is the neighbor sum distinguishing total chromatic number and denoted by χΣ″(G). Pilśniak and Woźniak conjectured that for any simple graph with maximum degree Δ(G)Δ(G), χΣ″(G)≤Δ(G)+3. It is known that for any simple planar graph, χΣ″(G)≤max{Δ(G)+3,14} and χΣ″(G)≤max{Δ(G)+2,16}. In this paper, by using the famous Combinatorial Nullstellensatz, we show that for any simple planar graph, χΣ″(G)≤max{Δ(G)+2,14}. The bound Δ(G)+2Δ(G)+2 is sharp.
Journal: Theoretical Computer Science - Volume 640, 9 August 2016, Pages 125–129