Minimum Sum Edge Colorings of Multicycles

Details Minimum Sum Edge Colorings of Multicycles Minimum Sum Edge Colorings of Multicycles

2007-06-26

arxiv.org/abs/0706.3848v2

Computer Science

Discrete Mathematics

Scientific paper

In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is minimum. The {\em chromatic edge strength} of a graph is the minimum number of colors required in a minimum sum edge coloring of this graph. We study the case of multicycles, defined as cycles with parallel edges, and give a closed-form expression for the chromatic edge strength of a multicycle, thereby extending a theorem due to Berge. It is shown that the minimum sum can be achieved with a number of colors equal to the chromatic index. We also propose simple algorithms for finding a minimum sum edge coloring of a multicycle. Finally, these results are generalized to a large family of minimum cost coloring problems.

Affiliated with

Also associated with

No associations

Rating

Minimum Sum Edge Colorings of Multicycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Sum Edge Colorings of Multicycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Sum Edge Colorings of Multicycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-506207