2007/06/26 by Jean Cardinal, Cardinal, Jean, Vlady Ravelomanana +3
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #cs.DM
paper · pdf · doi:10.48550/arxiv.0706.3848
arxiv created 2008/01/22 · arxiv updated 2009/12/01
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.