The edge-distinguishing chromatic number of spider graphs with three legs or bounded leg lengths

Abstract

The edge-distinguishing chromatic number \(\lambda(G)\) of a simple graph \(G\) is the minimum number of colors \(k\) assigned to the vertices in \(V(G)\) such that each edge \(\{u_i, u_j\}\) corresponds to a different set \(\{c(u_i), c(u_j)\}\). Al-Wahabi et al.\ derived an exact formula for the edge-distinguishing chromatic number of a path and of a cycle. We derive an exact formula for the edge-distinguishing chromatic number of a spider graph with three legs and of a spider graph with \(\Delta\) legs whose lengths are between 2 and \(\frac{\Delta+3}{2}\).