VERTEX-DISTINGUISHING PROPER EDGE-COLORINGS

An edge-coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge-col oring of a simple graph G is denoted by chi(s)'(G) A simple count show s that chi(s)'(G) greater than or equal to max{(i!n(i))(1/i) : 1 less than or equal to i less than or equal to Delta} where n(i) denotes the number of vertices of degree i in G. We prove that chi(s)'(G) less th an or equal to C max{n(i)(1/i) : 1 less than or equal to i less than o r equal to Delta} where C is a constant depending only on Delta. Some results for special classes of graphs, notably trees, are also present ed. (C) 1997 John Wiley & Sons, Inc.