4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't know if it matters much, but would you consider a cyclic order on the colors? $\endgroup$
    – Aaron Meyerowitz
    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

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .