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 pp-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)χ′(G) of a (multi)graph GG with maximum degree Δ(G)Δ(G) and maximum multiplicity μ(G)μ(G) satisfies Δ(G)≤χ′(G)≤Δ(G)+μ(G)Δ(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Δ(G)=2μ(G)+1≥5. In this paper we discuss the problem: For which values Δ,μΔ,μ does there exist a graph GG satisfying Δ(G)=ΔΔ(G)=Δ, μ(G)=μμ(G)=μ, and χ′(G)=Δ+μχ′(G)=Δ+μ.