The irregular coloring number of a tree

AbstractAn edge-coloring of a graph G is called vertex-distinguishing if for any two distinct vertices the multisets of colors assigned to incident edges differ. Let c(G) be the minimum number of colors necessary for such a coloring, and let ni denote the number of vertices of degree i in G. A simple count shows that c(G) ⩾ max {n1, C1n212}. We prove that if G is a tree then c(G) ⩽ max {n1, C2n212}