“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