TY - JOUR
T1 - List edge and list total colourings of multigraphs
AU - Borodin, O. V.
AU - Kostochka, A. V.
AU - Woodall, D. R.
N1 - Funding Information:
-The work of the second author was partly supported by Grant 96-01-01614 of the Russian Foundation for Fundamental Research and by the Network DIMANET of the European Union.
Funding Information:
* This work was carried out while the first author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR K00561 from the Engineering and Physical Sciences Research Council.
PY - 1997/11
Y1 - 1997/11
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031280748&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031280748&partnerID=8YFLogxK
U2 - 10.1006/jctb.1997.1780
DO - 10.1006/jctb.1997.1780
M3 - Article
AN - SCOPUS:0031280748
SN - 0095-8956
VL - 71
SP - 184
EP - 204
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -