Improving a Family of Approximation Algorithms to Edge Color Multigraphs

Given a multigraph G=(V,E), the Edge Coloring Problem (ECP) calls for the minimum number X of colors needed to color the edges in E so that all edges incident with a common node are assigned different colors. The best known polynomial time approximation algorithms for ECP belong to a same family, which is likely to contain, for each positive integer k, an algorithm which uses at most ((2k+1)X+(2k-2))/2k (rounded up) colors. For k<= 5 the existence of the corresponding 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)X+(2k-3))/2k (rounded up) 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-known conjectures on ECP are valid.