r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, chi '(s) (G, r) denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, chi '(s) (T, 1) <=Delta(T) + 1. Here we generalize this result and show that chi '(s)(T, 2) <=Delta(T) + 1. Moreover, we show that if for any two vertices u and v with maximum degree d(u, v) >= 3, then chi '(s) (T, 2) = Delta(T). Also for any tree T with J (T) >= 3 we,s prove that chi '(s) (T, 3) <= 2 Delta(T) - 1. Finally, it is shown that for any graph G with no isolated edges, chi '(s) (G, 1) <= 3 Delta(G). (c) 2006 Elsevier B.V. All rights reserved.