A Characterization of Multigraphs Reaching Goldberg's Bound of Chromatic Index

ABSTRACT Let be a finite, loopless graph that may contain multiedges. We call a ring graph if is obtained from a cycle by duplicating some edges. Denote by and the chromatic index and maximum degree of , respectively. Kőnig's classical result implies that if is a bipartite graph. Goldberg showed that , where is the length of a shortest odd cycle of . Stiebitz, Scheide, Toft, and Favrholdt conjectured that if reaches this upper bound, then contains a ring graph as a subgraph with the same chromatic index. Cao, Chen, He, and Jing found some counterexamples for the conjecture. In this paper, we establish a necessary and sufficient condition for the conjecture of Stiebitz et al. to hold. More specifically, writing with in the division‐remainder form, we show that if then the conjecture holds, otherwise the conjecture fails. If graph has an odd number of vertices, a matching of covering all, but one, vertices of is called a near‐perfect‐matching of . We characterize ring graphs, as well as ‐graphs, that have a near‐perfect‐matching factorization, and use these decomposition theorems to obtain the above characterization of the truth of the conjecture of Stiebitz, Scheide, Toft, and Favrholdt.