MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.