On Vizing’s bound for the chromatic index of a multigraph

Two of the basic results on edge coloring are Vizing’s Theorem [V.G. Vizing, On an estimate of the chromatic class of a p -graph, Diskret. Analiz. 3 (1964) 25–30 (in Russian); V.G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965) 29–39 (in Russian). English translation in Cybernetics 1 32–41], which states that the chromatic index χ ′ ( G ) of a (multi)graph G with maximum degree Δ ( G ) and maximum multiplicity μ ( G ) satisfies Δ ( G ) ≤ χ ′ ( G ) ≤ Δ ( G ) + μ ( G ) , and Holyer’s Theorem [I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718–720], which states that the problem of determining the chromatic index of even a simple graph is NP-hard. Hence, a good characterization of those graphs for which Vizing’s upper bound is attained seems to be unlikely. On the other hand, Vizing noticed in the first two above-cited references that the upper bound cannot be attained if Δ ( G ) = 2 μ ( G ) + 1 ≥ 5 . In this paper we discuss the problem: For which values Δ , μ does there exist a graph G satisfying Δ ( G ) = Δ , μ ( G ) = μ , and χ ′ ( G ) = Δ + μ .