Neighbor Sum Distinguishing Total Chromatic Number of Planar Graphs without 5-Cycles

Abstract

For a given graph G = (V (G), E(G)), a proper total coloring ϕ: V (G) ∪ E(G) → {1, 2, . . . , k} is neighbor sum distinguishing if f(u) ≠ f(v) for each edge uv ∈ E(G), where f(v) = Σuv∈E(G) ϕ(uv)+ϕ(v), v ∈ V (G). The smallest integer k in such a coloring of G is the neighbor sum distinguishing total chromatic number, denoted by χΣ″(G)\chi _\Sigma ^{''} ( G ) . Pilśniak and Woźniak first introduced this coloring and conjectured that χΣ″(G)≤Δ(G)+3\chi _\Sigma ^{''} ( G ) \le \Delta ( G ) + 3 for any graph with maximum degree Δ(G). In this paper, by using the discharging method, we prove that for any planar graph G without 5-cycles, χΣ″(G)≤max{Δ(G)+2, 10}\chi _\Sigma ^{''} ( G ) \le \max \left\{ {\Delta ( G ) + 2,\;10} \right\} . The bound Δ(G) + 2 is sharp. Furthermore, we get the exact value of χΣ″(G)\chi _\Sigma ^{''} ( G ) if Δ(G) ≥ 9.

Keywords

• neighbor sum distinguishing total coloring
• discharging method
• planar graph
• 05c15