List Colorings with Distinct List Sizes, the Case of Complete Bipartite Graphs

Let f : V → N be a function on the vertex set of the graph G = ( V , E ) . The graph G is f‐choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number,χ s c( G ) , is the minimum of ∑ f ( v ) , over all functions f such that G is f ‐choosable. It is known (Alon, Surveys in Combinatorics, 1993 (Keele), London Mathematical Society Lecture Note Series, Vol. 187, Cambridge University Press, Cambridge, 1993, pp. 1–33, Random Struct Algor 16 (2000), 364–368) that if G has average degree d , then the usual choice numberχ ℓ ( G )is at least Ω ( log d ) , so they grow simultaneously. In this article, we show thatχ s c( G ) / | V ( G ) |can be bounded while the minimum degreeδ min ( G ) → ∞ . Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph K a , q .