On Edge Coloring of Multigraphs

Let $\mathrm{\Delta }(G)$ and ${\chi }^{\mathrm{\prime }}(G)$ be the maximum degree and chromatic index of a graph $G$, respectively. Appearing in different forms, Gupta,(1967), Goldberg,(1973), Andersen,(1977), and Seymour,(1979) made the following conjecture: Every multigraph $G$ satisfies ${\chi }^{\mathrm{\prime }}(G)\le \max \{\mathrm{\Delta }(G)+1,\mathrm{\Gamma }(G)\}$, where $\mathrm{\Gamma }(G)={\max }_{H\subseteq G,\mathrm{\mid }V(H)\mathrm{\mid }\ge 2}\lceil \frac{\mathrm{\mid }E(H)\mathrm{\mid }}{\lfloor \frac{1}{2}\mathrm{\mid }V(H)\mathrm{\mid }\rfloor }\rceil$ is the density of $G$. In this paper, we present a polynomial-time algorithm for coloring any multigraph with $\max \{\mathrm{\Delta }(G)+1,\mathrm{\Gamma }(G)\}$ colors, confirming the conjecture algorithmically. Since ${\chi }^{\mathrm{\prime }}(G)\ge \max \{\mathrm{\Delta }(G),\mathrm{\Gamma }(G)\}$, this algorithm gives a proper edge coloring that uses at most one more color than the optimum. As determining the chromatic index of an arbitrary graph is $NP$-hard, the $\max \{\mathrm{\Delta }(G)+1,\mathrm{\Gamma }(G)\}$ bound is best possible for efficient proper edge coloring algorithms on general multigraphs, unless $P=NP$. Related work of Chen, Hao, Yu, and Zang have also obtained an algorithm using similar high-level ideas; the present approach establishes a complete proof.