Authors:
C.-Q. Xu, X. Zhao
Title:
Neighbor sum distinguishing total chromatic number of planar graphs without 5-cycles
Source:
Discussiones Mathematicae Graph Theory
Received 05.12.2017, Revised 08.02.2018, Accepted 07.03.2018, doi: 10.7151/dmgt.2122

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). Pil'{s}niak and Wo'{z}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.
Keywords:
neighbor sum distinguishing total coloring, discharging method, planar graph

Links:
PDF