r-Strong edge colorings of graphs

Let G be a graph and for any natural number r  , χ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, χs′(T,1)⩽Δ(T)+1. Here we generalize this result and show that χs′(T,2)⩽Δ(T)+1. Moreover, we show that if for any two vertices uu and vv with maximum degree d(u,v)⩾3d(u,v)⩾3, then χs′(T,2)=Δ(T). Also for any tree T   with Δ(T)⩾3Δ(T)⩾3 we prove that χs′(T,3)⩽2Δ(T)-1. Finally, it is shown that for any graph G   with no isolated edges, χs′(G,1)⩽3Δ(G).