Hi everyone,

I have a problem I am working on that can be reduced to the following special case of edge coloring.

Let $G = (V,E)$ be an arbitrary graph. Furthermore, let each edge be assigned a positive integer so that we have function $w: E \rightarrow N$. Let $C$ be a set of colors, represented by an interval of integers. Can we assign a coloring to the edges of $G$ so that for each each $e$, if $w(e) = a$ then $e$ receives $a$ colors, the colors assigned to $e$ form an interval of the color set, and no edge shares a color with another incident edge. (Alteratively, is there an approximation factor similar to the one given Vizing's theorem for the standard edge-coloring problem).

I have done a bunch of literature searches and have already discovered that this problem is not the same as: interval edge coloring (close but not that close) and weighted edge coloring (closer but generally only applicable to bipartite graphs).

Has anyone seen this problem before? Are there any results? Would you recommend any references or perhaps additional directions to search.

Many thanks, Scott

  • $\begingroup$ I don't know if it matters much, but would you consider a cyclic order on the colors? $\endgroup$ Commented Dec 22, 2010 at 23:52
  • $\begingroup$ The trivial bounds are $\Delta(G)\le C(G)\le 6\Delta(G)$ where $\Delta(G)$ is the maximal weighted degree. What you, probably, want, is something like $C(G)\le\Delta(G)+W$ where $W=\max_e w(e)$, right? $\endgroup$
    – fedja
    Commented Dec 23, 2010 at 0:58

2 Answers 2


The question is a little vague. The maximum degree (with weights) is a lower bound. If you took off the the condition that the colors assigned to an edge are themselves an interval then it would be Vizing's problem in a graph with possible multiple edges so maximum degree or maximum degree plus 1. It might help to think of each edge getting just one color (an integer, the smallest color assigned in your scheme) and the first number $w(e)$ specifying how seperated that color has to be from any incident color.

I'd start with the case that $w(e)$ is a constant $q$. Then Vizing's theorem would give that $q\Delta+q$ colors suffice where $\Delta$ is the maximum degree of the underlying graph. I imagine that sometimes that number would be needed. This leads me to a rash

Conjecture: label each vertex $v$ with $\max w(e)+\Sigma w(e)$ where the max and sum are over the edges incident with it. Then the greatest label is a number of colors which suffices and sometimes is necessary.


(Just a comment, but didn't have enough rep.)

Replace each edge $e = (u,v)$ with $w(e)$ multiple edges between $u$ and $v$. Then your problem is simply the problem of edge coloring a multi-graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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