List edge and list total colourings of multigraphs (Q1366604): Difference between revisions

This paper exploits the remarkable new method of \textit{F. Galvin} [J. Comb. Theory, Ser. B 63, No. 1, 153-158 (1995; Zbl 0826.05026)], who proved that the list edge chromatic number \(\chi_{\text{list}}'(G)\) of a bipartite multigraph \(G\) equals its edge chromatic number \(\chi'(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)\}+ \lfloor{1\over 2}\min\{d(u),d(w)\}\rfloor\) colours, then the same holds; in particular, if \(G\) has maximum degree \(\Delta=\Delta(G)\) then \(\chi_{\text{list}}'(G)\leq\lfloor{3\over 2}\Delta\rfloor\). Sufficient conditions are given in terms of the maximum degree and maximum average degree of \(G\) in order that \(\chi_{\text{list}}'(G)=\Delta\) and \(\chi''_{\text{list}}(G)= \Delta+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 \(\Delta\geq 12\) then \(\chi_{\text{list}}'(G)=\Delta\) and \(\chi''_{\text{list}}(G)=\Delta+1\).