Portal de Periódicos da CAPES

List Edge and List Total Colourings of Multigraphs

1997; Elsevier BV; Volume: 71; Issue: 2 Linguagem: Inglês

10.1006/jctb.1997.1780

1096-0902

O. V. Borodin, Alexandr Kostochka, Douglas R. Woodall,

graph theory and CDMA systems

This paper exploits the remarkable new method of Galvin (J. Combin. Theory Ser. B63(1995), 153–158), who proved that the list edge chromatic numberχ′list(G) of a bipartite multigraphGequals its edge chromatic numberχ′(G). It is now proved here that if every edgee=uwof a bipartite multigraphGis assigned a list of at least max{d(u), d(w)} colours, thenGcan be edge-coloured with each edge receiving a colour from its list. If every edgee=uwin an arbitrary multigraphGis assigned a list of at least max{d(u), d(w)}+⌊12min{d(u), d(w)}⌋ colours, then the same holds; in particular, ifGhas maximum degreeΔ=Δ(G) thenχ′list(G)⩽⌊32Δ⌋. Sufficient conditions are given in terms of the maximum degree and maximum average degree ofGin order thatχ′list(G)=Δandχ″list(G)=Δ+1. Consequences are deduced for planar graphs in terms of their maximum degree and girth, and it is also proved that ifGis a simple planar graph andΔ⩾12 thenχ′list(G)=Δandχ″list(G)=Δ+1.