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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.