Asymptotically Good Choice Numbers of Multigraphs

P.Mark Kayll1
1Department of Mathematical Sciences, University of Montana Missoula MT 59812-1032, USA

Abstract

For loopless multigraphs \(G\), the total choice number is asymptotically equal to its fractional counterpart as the latter invariant tends to infinity. If \(G\) is embedded in the plane, then the edge-face and entire choice numbers exhibit the same “asymptotically good” behaviour. These results are based mainly on an analogous theorem of Kahn [5] for the list-chromatic index. Together with work of Kahn and others, our three results give a complete answer to a natural question: which of the seven invariants associated with list-colouring the nonempty subsets of \(\{V, E, F\}\) are asymptotically good?