Upper bounds for adjacent vertex-distinguishing edge coloring (Q1702826)

A proper edge \(k\)-coloring \(f\) of a graph \(G\) is a mapping from the edge set of \(G\) to the set \(\{1, 2, \dots, k\}\) such that no two adjacent edges receive the same color. For a vertex \(v\in V(G)\) let \(F_f(v)\) denote the set of colors of edges incident to \(v\). A proper edge \(k\)-coloring is called an adjacent vertex-distinguishing \(k\)-edge coloring if for every edge \(uv\) in \(G\) is \(F_f(u)\neq F_f(v)\). The smallest \(k\) for which an adjacent vertex-distinguishing edge coloring of \(G\) using \(k\) colors exists is called adjacent vertex-distinguishing chromatic number of \(G\) and is denoted by \(\chi^{'}_{as}(G)\). \textit{Z. Zhang} et al. [Appl. Math. Lett. 15, No. 5, 623--626 (2002; Zbl 1008.05050)] conjectured that for any connected graph \(G\) with at least three vertices different from \(C_5\) is \(\chi^\prime_{as}(G)\leq \Delta(G)+2\). In the given paper, the authors presented an upper bound for this graph parameter and showed that for every connected graph \(G\) with maximum degree \(\Delta(G)\geq 3\) is \(\chi^\prime_{as}(G)\leq 3\Delta(G)-1\). Moreover, they proved that if \(G\) is a graph with maximum degree \(\Delta(G)\geq 458\) and minimum degree \(\delta(G)\geq 8\sqrt{\Delta(G) \ln \Delta(G)}\) then \(\chi^\prime_{as}(G)\leq \Delta(G)+1+5\sqrt{\Delta(G) \ln \Delta(G)}\).