On Edge Coloring of Multigraphs

Abstract

Let $\hat{I}”(G)$ and $\ddot{I}{‡}^{\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 $\ddot{I}{‡}^{\prime }(G)\le \max \{\hat{I}”(G)+1,\hat{I}“(G)\}$, where $\hat{I}“(G)={\max }_{H\subseteq G,|V(H)|\ge 2}\lceil \frac{|E(H)|}{\lfloor \frac{1}{2}|V(H)|\rfloor }\rceil$ is the density of $G$. In this paper, we present a polynomial-time algorithm for coloring any multigraph with $\max \{\hat{I}”(G)+1,\hat{I}“(G)\}$ colors, confirming the conjecture algorithmically. Since $\ddot{I}{‡}^{\prime }(G)\ge \max \{\hat{I}”(G),\hat{I}“(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 \{\hat{I}”(G)+1,\hat{I}“(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.