# 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))$$?

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$$.