Vertex-distinguishing and sum-distinguishing edge coloring of regular graphs

Abstract

Given an integer $k\ge 1$, an edge-$k$-coloring of a graph $G$ is an assignment of $k$ colors $1,\dots ,k$ to the edges of $G$ such that no two adjacent edges receive the same color. A vertex-distinguishing (resp. sum-distinguishing) edge-$k$-coloring of $G$ is an edge-$k$-coloring such that for any two distinct vertices $u$ and $v$, the set (resp. sum) of colors taken from all the edges incident with $u$ is different from that taken from all the edges incident with $v$. The vertex-distinguishing chromatic index (resp. sum-distinguishing chromatic index), denoted ${\chi }_{vd}^{\prime }(G)$ (resp. ${\chi }_{sd}^{\prime }(G)$), is the smallest value $k$ such that $G$ has a vertex-distinguishing-edge-$k$-coloring (resp. sum-distinguishing-edge-$k$-coloring). Let $G$ be a $d$-regular graph on $n$ vertices, where $n$ is even and sufficiently large. We show that ${\chi }_{vd}^{\prime }(G)=d+2$ if $d$ is arbitrarily close to $n/2$ from above, and ${\chi }_{sd}^{\prime }(G)=d+2$ if $d\ge \frac{2n}{3}$. Our first result strengthens a result of Balister et al. in 2004 for such class of regular graphs, and our second result constitutes a significant advancement in the field of sum-distinguishing edge coloring. To achieve these results, we introduce novel edge coloring results which may be of independent interest.

24pages. arXiv admin note: substantial text overlap with arXiv:2405.07382