Precoloring extension of Vizing's Theorem for multigraphs.

Let G be a graph with maximum degree Δ (G) and maximum multiplicity μ (G). Vizing and Gupta, independently, proved in the 1960s that the chromatic index of G is at most Δ (G) + μ (G). The distance between two edges e and f in G is the length of a shortest path connecting an endvertex of e and an endvertex of f. A distance- t matching is a set of edges having pairwise distance at least t. Albertson and Moore conjectured that if G is a simple graph, using the palette { 1 , ... , Δ (G) + 1 } , any precoloring on a distance-3 matching can be extended to a proper edge coloring of G. Edwards et al. proposed the following stronger conjecture: For any graph G , using the palette { 1 , ... , Δ (G) + μ (G) } , any precoloring on a distance-2 matching can be extended to a proper edge coloring of G. Girão and Kang verified the conjecture of Edwards et al. for distance-9 matchings. In this paper, we improve the required distance from 9 to 3 for multigraphs G with μ (G) ≥ 2. [ABSTRACT FROM AUTHOR]