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 $\chi$ 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 $\lc((2k+1)\chi+(2k-2))/2k\rc$ colors. For $k\leq 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 $\lc((2k+1)\chi+(2k-3))/2k\rc$ 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.