The strict neighbor-distinguishing index of simple graphs with maximum degree five

Abstract

Suppose that $\varphi$ is a proper edge-$k$-coloring of the graph $G$. For a vertex $v\in V(G)$, let $C_{\varphi }(v)$ denote the set of colors assigned to the edges incident with $v$. The proper edge-$k$-coloring $\varphi$ of $G$ is strict neighbor-distinguishing if for any adjacent vertices $u$ and $v$, $C_{\varphi }(u)⊊C_{\varphi }(v)$ and $C_{\varphi }(v)⊊C_{\varphi }(u)$. The strict neighbor-distinguishing index, denoted ${\chi }_{snd}^{\prime }(G)$, is the minimum integer $k$ such that $G$ has a strict neighbor-distinguishing edge-$k$-coloring. In this paper we prove that if $G$ is a simple graph with maximum degree five, then ${\chi }_{snd}^{\prime }(G)\le 12$.