IMPROVING A FAMILY OF APPROXIMATION ALGORITHMS TO EDGE COLOR MULTIGRAPHS

Given a multigraph G = (V, E), the Edge Coloring Problem (ECP) calls f or the minimum number chi of colors needed to color the edges in E so that all edges incident with a common node are assigned different colo rs. The best known polynomial time approximation algorithms for ECP be long to a same family, which is likely to contain, for each positive i nteger k, an algorithm which uses at most [((2k + 1)chi + (2k - 2))/2k ] colors. For k less than or equal to 5 the existence of the correspon ding algorithm was shown, whereas for larger values of k the question is open. We show that, for any k such that the corresponding algorithm exists, it is possible to improve the algorithm so as to use at most [((2k + 1)chi + (2k - 3))/2k] colors. It is easily shown that the (2k - 3)/2k term cannot be reduced further, unless P = NP. We also discuss how our result can be used to extend the set of cases in which well-k nown conjectures on ECP are valid. (C) 1998 Elsevier Science B.V. All rights reserved.