2015/07/27 by Loeb, Sarah, Przybyło, Jakub, Tang, Yunfang
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1507.07573
Given a proper total k-coloring c:V(G)∪ E(G)→\1,2,…,k\ of a graph G, we define the value of a vertex v to be c(v) + ∑uv ∈ E(G) c(uv). The smallest integer k such that G has a proper total k-coloring whose values form a proper coloring is the neighbor sum distinguishing total chromatic number of G, χ"Σ(G). Pilśniak and Woźniak (2013) conjectured that χ"Σ(G)≤ Δ(G)+3 for any simple graph with maximum degree Δ(G). In this paper, we prove this bound to be asymptotically correct by showing that χ"Σ(G)≤ Δ(G)(1+o(1)). The main idea of our argument relies on Przybyło's proof (2014) regarding neighbor sum distinguishing edge-colorings.