Resolving Edge Colorings in Graphs

Abstract

For edges $e$ and $f$ in a connected graph $G$, the distance $d(e,f)$ between $e$ and $f$ is the minimum nonnegative integer $n$ for which there exists a sequence $e=e_0,e_1,\dots ,e_l=f$ of edges of $G$ such that $e_i$ and $e_{i+1}$ are adjacent for $i=0,1,\dots ,l-1$. Let $c$ be a proper edge coloring of $G$ using $k$ distinct colors and let $D=\{C_1,C_2,\dots ,C_k\}$ be an ordered partition of $E(G)$ into the resulting edge color classes of $c$. For an edge $e$ of $G$, the color code $c_D(e)$ of $e$ is the $k$-tuple $(d(e,C_1),d(e,C_2),\dots ,d(e,C_k))$, where $d(e,C_i)=min\{d(e,f):f\in C_i\}$ for $1\le i\le k$. If distinct edges have distinct color codes, then $c$ is called a resolving edge coloring of $G$. The resolving edge chromatic number ${\chi }_{re}(G)$ is the minimum number of colors in a resolving edge coloring of $G$. Bounds for the resolving edge chromatic number of a connected graph are established in terms of its size and diameter and in terms of its size and girth. All nontrivial connected graphs of size $m$ with resolving edge chromatic number $3$ or $m$ are characterized. It is shown that for each pair $k,m$ of integers with $3\le k\le m$, there exists a connected graph $G$ of size $m$ with ${\chi }_{re}(G)=k$. Resolving edge chromatic numbers of complete graphs are studied.