LIST EDGE AND LIST TOTAL COLORINGS OF MULTIGRAPHS

This paper exploits the remarkable new method of Galvin (J. Combin. Th eory Ser. B 63 (1995), 153-158), who proved that the list edge chromat ic number chi'(list)(G) of a bipartite multigraph G equals its edge ch romatic number chi'(G). It is now proved here that if every edge e = u w 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)} + [1/2min {d(u), d(w )}] colours, then the holds; in particular, if G has maximum degree De lta = Delta(G) then chi'(list)(G) less than or equal to [3/2 Delta]. S ufficient conditions are given in terms of the maximum degree and maxi mum average degree of G in order that chi'(list)(G) = Delta and chi'(l ist)(G) = Delta + 1. Consequences are deduced for planar graphs in ter ms of their maximum degree and girth, and it is also proved that if G is a simple planar graph and Delta greater than or equal to 12 then ch i'(list)(G)=Delta and chi'(list)(G)= Delta + 1. (C) 1997 Academic Pres s.