Résumé | Let us consider a proper coloring f of edges in a simple graph G=(V,E). Such a coloring defines for each vertex $xin V$ the palette of colors, i.e., the set of colors of edges incident with x, denoted by S(x). Two vertices x and y are similar if S(x)=S(y). The minimum number of colors required in a proper coloring f without two similar vertices is called the vertex-distinguishing index, and is denoted by vdi(G). The vertex-distinguishing index was introduced and studied (as ``observability'' of a graph) by Cerny, Hornak and Sotak and, independently, (as ``strong coloring") by Burris and Schelp. In general, for some families of graphs, the vertex-distinguishing index can be much greater than the maximum degree. For instance, consider a vertex-distinguishing coloring of a cycle of length n with k colors. Since each palette is of size two, and the number of all possible palettes cannot be smaller than $n$, we have ${kchoose 2}ge n $. Hence, $vdi(C_n) ge sqrt{2n}$. However, if we distinguish the vertices in another way, namely by sets of color walks starting from vertices, not just by their palettes, then the number of colors we need is very close to the chromatic index. Some relationships to other `distinguishing' parameters will be discussed such as the distinguishing chromatic index, i.e., the minimum number of colors in a proper edge-coloring preserved only by the identity automorphism. |