2016/01/09 by Songling Shan, Shan, Songling, Bing Yao +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1601.02601
arxiv created 2016/01/09 · arxiv updated 2016/01/13
A proper edge coloring of a simple graph G is called a vertex distinguishing edge coloring (vdec) if for any two distinct vertices u and v of G, the set of the colors assigned to the edges incident to u differs from the set of the colors assigned to the edges incident to v. The minimum number of colors required for all vdecs of G is denoted by χ 's(G) called the vdec chromatic number of G. Let nd(G) denote the number of vertices of degree d in G. In this note, we show that a tree T with n2(T)≤ n1(T) holds χ 's(T)=n1(T)+1 if its diameter D(T)=3 or one of two particular trees with D(T) =4, and χ 's(T)=n1(T) otherwise; furthermore χ 'es(T)=χ 's(T) when |E(T)|≤ 2(n1(T)+1), where χ 'es(T) is the equitable vdec chromatic number of T.