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 132-41], which states that the chromatic index chi'(G) of a (multi)graph G with maximum degree Delta(G) and maximum multiplicity mu(G) satisfies Delta(G) <= chi'(G) <= Delta(G) + mu(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 Delta(G) = 2 mu(G) + 1 >= 5. In this paper we discuss the problem: For which values Delta, mu does there exist a graph G satisfying Delta(G) = Delta, mu(G) = mu, and chi'(G) = Delta + mu. (C) 2008 Elsevier B.V. All rights reserved.