Distant set distinguishing edge colourings of graphs

We consider the following extension of the concept of adjacent strong edge colourings of graphs without isolated edges. Two distinct vertices which are at distance at most r in a graph are called r-adjacent. The least number of colours in a proper edge colouring of a graph G such that the sets of colours met by any r-adjacent vertices in G are distinct is called the r-adjacent strong chromatic index of G and denoted by χa,r′(G). It has been conjectured that χa,1′(G)≤Δ+2 if G is connected of maximum degree Δ≥2 and non-isomorphic to C5, while Hatami proved that there is a constant C, C≤300, such that χa,1′(G)≤Δ+C if Δ>1020 [J. Combin. Theory Ser. B 95 (2005) 246-256]. We conjecture that a similar statement should hold for any r, i.e., that for each positive integer r there exist constants δ0 and C such that χa,r′(G)≤Δ+C for every graph without an isolated edge and with minimum degree δ≥δ0, and argue that a lower bound on δ is unavoidable in such a case (for r>2). Using the probabilistic method we prove such an upper bound to hold for graphs with δ≥ϵΔ, for every r and any fixed ε∈(0,1], i.e., in particular for regular graphs. We also support the conjecture by proving an upper bound χa,r′(G)≤(1+o(1))Δ for graphs with δ≥r+2.