Return to Question

TeX and text clarification

Source Link

edit approved Sep 12, 2013 at 12:24

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)$G = (V,E)$ be an arbitrary graph. Furthermore, let each edge be assigned a positive integer so that we have function $w(e): E \rightarrow N$$w: E \rightarrow N$. Let C$C$ be a set of colors, represented by an interval of integers. Can we assign a coloring to the edges of G$G$ so that for each each e$e$, if w(e) = a$w(e) = a$ then e$e$ receives a$a$ colors, the colors assigned to e$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.

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

Many thanks, Scott

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): 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).

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

Many thanks, Scott

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