This paper exploits the remarkable new method of Galvin (J. Combin. Theory Ser. B 63 (1995), 153 158), who proved that the list edge chromatic number /$ list (G) of a bipartite multigraph G equals its edge chromatic number /$(G). It is now proved here that if every edge e=uw of a bipartite multigraph G is assigned a list of at least max[d(u), d(w)] colours, then G can be edge-coloured with each edge receiving a colour from its list. If every edge e=uw in an arbitrary multigraph G is assigned a list of at least max[d(u), d(w)]+w 1 2 min[d(u), d(w)]x colours, then the same holds; in particular, if G has maximum degree 2=2(G) then /$ list (G) w 3 2 2x. Sufficient conditions are given in terms of the maximum degree and maximum average degree of G in order that /$ list (G)=2 and /" list (G)=2+1. Consequences are deduced for planar graphs in terms of their maximum degree and girth, and it is also proved that if G is a simple planar graph and 2 12 then /$ list (G)=2 and /" list (G)=2+1.
1997 Academic Press
1. Introduction
Let G=(V, E) be a multigraph with vertex-set V(G)=V and edge-set E(G)=E. If v # V and X V, we write N(X ) for the set of neighbours of vertices in X, and N(v) :=N ([v]). We write d(v)=d G (v) for the degree of article no. TB971780 184 0095-8956Γ97 25.00