On Edge Coloring of Multigraphs

Abstract

Let $\Delta (G)$ and ${\chi }^{\prime }(G)$ be the maximum degree and chromatic index of a graph $G$, respectively. Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) made the following conjecture: Every multigraph $G$ satisfies ${\chi }^{\prime }(G)\le \max \{\Delta (G)+1,\Gamma (G)\}$, where $\Gamma (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 \{\Delta (G)+1,\Gamma (G)\}$ colors, confirming the conjecture algorithmically. Since ${\chi }^{\prime }(G)\ge \max \{\Delta (G),\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 \{\Delta (G)+1,\Gamma (G)\}$ bound is best possible for efficient proper edge coloring algorithms on general multigraphs, unless $P=NP$. Chen, Hao, Yu, and Zang have also presented an algorithm using similar high-level ideas; the present approach establishes a complete proof. The proofs of Theorems 3.2 and 3.3 were also verified by an AI-assisted audit using OpenAI's GPT-6 Pro model in ChatGPT; all resulting comments and revisions were independently evaluated by