“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 | |||||||
