Asymptotically optimal neighbor sum distinguishing total colorings of graphs

Abstract

Given a proper total $k$-coloring $c:V(G)\cup E(G)\to \{1,2,\dots ,k\}$ of a graph $G$, we define the value of a vertex $v$ to be $c(v)+{\sum }_{uv\in 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$, $\chi {"}_{\Sigma }(G)$. Pilśniak and Woźniak (2013) conjectured that $\chi {"}_{\Sigma }(G)\le \Delta (G)+3$ for any simple graph with maximum degree $\Delta (G)$. In this paper, we prove this bound to be asymptotically correct by showing that $\chi {"}_{\Sigma }(G)\le \Delta (G)(1+o(1))$. The main idea of our argument relies on Przybyło's proof (2014) regarding neighbor sum distinguishing edge-colorings.