## “School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 7722
School of Mathematics
Title:   r-strong edge colorings of graphs
Author(s):
 1 S. Akbari 2 H. Bidkhori 3 N. Nosrati
Status:   Published
Journal: Discrete Math.
Vol.:  306
Year:  2006
Pages:   3005-3010
Supported by:  IPM
Abstract:
Let G be a graph and for any natural number rs(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
scroll left or right