Minimum sum edge colorings of multicycles |
| |
Authors: | Jean Cardinal Vlady Ravelomanana |
| |
Institution: | a Université Libre de Bruxelles (ULB), CP 212, Bld. du Triomphe, B-1050 Brussels, Belgium b Laboratoire d’Informatique de l’Université Paris-Nord (LIPN), 99 Av. J.-B. Clément, 93430 Villetaneuse, France |
| |
Abstract: | 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 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. |
| |
Keywords: | Graph coloring Minimum sum coloring Chromatic strength |
本文献已被 ScienceDirect 等数据库收录! |
|