Elsevier

Discrete Mathematics

Volume 306, Issue 23, 6 December 2006, Pages 3005-3010
Discrete Mathematics

r-Strong edge colorings of graphs

https://doi.org/10.1016/j.disc.2004.12.027Get rights and content
Under an Elsevier user license
open archive

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 [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623–626] 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).

MSC

05C05
05C15

Keywords

Coloring
Strong edge coloring
Tree

Cited by (0)