The irregular coloring number of a tree (Q1894778)

An edge-coloring of a graph \(G = (V,E)\) is vertex-distinguishing, if for every edge \((v,w) \in E\), the multiset of colors assigned to edges incident to \(v\) differs from the multiset of colors assigned to edges incident to \(w\). The minimum number of colors of a vertex-distinguishing edge-coloring of \(G\) is the irregular coloring number of \(G\), denoted by \(c(G)\). If \(n_i(G)\) denotes the number of vertices in \(G\) of degree \(i\), then an easy argument shows that \(c(G) \geq \max \bigl(n_1(G), \sqrt {2n_2 (G)}- {1\over 2}\bigr)\). The main result of this paper is a proof, that for every tree \(T\) with at least three vertices, \(c(T) \leq \max \bigl(n_1(T), 4.62 \sqrt {n_2 (T)}, 8\bigr) + 1\). The proof is constructive, and provides an algorithm that produces the required vertex-distinguishing coloring.