The universal labeling of graph The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ 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,\ldots, k\}$ denoted it by $\overrightarrow{\chi_{u}}(G) $.
Every graph has some  universal labelings, for example one may put the different powers of two $(1,2,2^2,\ldots,2^{n-1})$ on the edges of $G$.
Let $f $ be a proper edge coloring for a given graph $G$. Then the function $\ell:E(G)\rightarrow 2^{f(e)-1}$ is a universal labeling for a graph $G$. By Vizing's theorem, the chromatic index of a graph $G$ is equal to either $ \Delta(G) $ or $ \Delta(G) +1 $. So, every graph $G$ has a universal labeling from $\{1,2,\ldots, 2^{\Delta(G)}\}$. On the other hand,  note that every universal labeling for the edges of $G$ is a  proper edge coloring of $G$. Therefore the universal labeling number is at least the chromatic index of a graph. Therefore we have the following bound.
\begin{equation}
\Delta(G) \leq \overrightarrow{\chi_{u}} (G)\leq  2^{\Delta(G)}.
\end{equation}
My  question: Is there  a polynomial function $f$, such that, for every graph $G$, $\overrightarrow{\chi_{u}} (G)\leq f(\Delta(G))$?
 A: You can get a slightly better upperbound than $\overrightarrow{\chi_{u}} (G)\leq  2^{\Delta(G)}$ by using sets of integers with distinct subset sums.  For example, Bohman constructed a set $S$ of $n$ positive integers with $2^n$ distinct subset sums and with maximum element less than $0.22002\cdot2^{n}$.  By taking a proper edge-colouring and assigning labels from $S$ rather than powers of $2$, we have that $\overrightarrow{\chi_{u}} (G)\leq 0.44004 \cdot 2^{\Delta(G)}$.
You can also get slightly better lowerbounds as follows. Define a set $S$ of positive integers to be good if for all $s \in S$, there does not exist a set $T \subseteq S \setminus \{s\}$ such that $s = \sum_{t \in T} t$. For all $n \in \mathbb{N}$, let $$g(n)=\min \{\max S : \text{$S$ is a good set of $n$ positive integers}\}.$$
Claim. For all graphs $G$,
$$\overrightarrow{\chi_{u}} (G) \geq  g({\Delta(G))}.$$
Proof. Let $x$ be a vertex of $G$ of maximum degree and let $S$ be the set of $\Delta(G)$ labels that appear on the edges incident to $x$. By definition, $S$ must be a good set.  Therefore, $\overrightarrow{\chi_{u}} (G) \geq \max S \geq g(\Delta(G))$, as claimed.
I initially thought that $g(n)$ might be superpolynomial in $n$, but I now realize that $\{n-1, n, \dots, 2n-2\}$ is a good set of size $n$.  Therefore, $g(n) \leq 2n-2$.
