MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

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

share|cite|improve this question
I don't know if it matters much, but would you consider a cyclic order on the colors? – Aaron Meyerowitz Dec 22 '10 at 23:52
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? – fedja Dec 23 '10 at 0:58

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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

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