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

Zhao, Xue ; Xu, Chang-Qing 

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 243-253

Résumé

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). Pilśniak and Woźniak first introduced this coloring and conjectured that χ_Σ^”(G) ≤Δ (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 }. The bound Δ (G) + 2 is sharp. Furthermore, we get the exact value of χ_Σ^” (G) if Δ (G) ≥ 9.

Détail

Keywords: neighbor sum distinguishing total coloring, discharging method, planar graph