“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 7722  


Abstract:  
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 [9] 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 u and v with
maximum degree d(u,v) ≥ 3, then
χ^{′}_{s}(T,2)=∆(T). Also for any tree T with
∆(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).
Download TeX format 

back to top 