Is there any polynomial upper bound for the universal labeling of graphs? (Q1680487)

In this paper, the authors discuss universal labelings. In the introductory part, the authors recollect neighbour-sum-distinguishing labelings, edge-labelings, vertex distinguishing colorings and universal labelings. A universal labeling of a graph \(G\) is a labeling of the set of edges in \(G\) such that in every orientation \(l\) of \(G\) for every two adjacent vertices \(v\) and \(u\), the sum of incoming edges of \(v\) and \(u\) in the oriented graph are different from each other. The universal labeling number of a graph \(G\) is the minimum number \(k\) such that \(G\) has universal labeling from \(\{1,2,\dots,k\}\) denoted it by \(\vec{\chi_{u}}(G)\). They have proved that \(2\Delta(G)-2 \leq \vec{\chi_{u}} \leq 2^{\Delta(G)}\), where \(\Delta(G)\) denotes the maximum degree of \(G\). \textit{M. Karoński} et al. [J. Comb. Theory, Ser. B 91, No. 1, 151--157 (2004; Zbl 1042.05045)] conjectured that every graph with no isolated edge has a neighbour-sum-distinguishing labeling from \(N_{3}\) (1-2-3-conjecture). In Section 2, motivated by 1-2-3-conjecture, the authors propose Problem 1: ``Is there any polynomial function \(f\) such that \(\vec{\chi_{u}}(G) \leq f(\Delta(G))\) for every graph \(G\)?''. The authors discuss the ``yes'' and ``no'' instances of this problem. Also they prove some lower and upper bounds. Then, they discuss Problem 1 if \(G\) is a complete graph or a star. Also, the authors prove that \(\vec{\chi_{u}}(T)=O(\Delta^{3})\) for every tree \(T\). Next, the authors prove that for a given 3-regular graph \(G\), the universal labeling number of \(G\) is 4 under certain conditions. Therefore, for a given 3-regular graph \(G\), it is shown to be NP-complete to determine whether the universal labeling number of \(G\) is 4. Finally, using probabilistic methods, they confirm a weaker version of the conjecture. This paper is very well organized. There is clarity of thought throughout the paper. This paper contains details of universal labelings with which researchers can enter into research in the area of graph labelings. Researchers in the area of universal labelings will be greatly benefit from reading this paper.