List colorings with distinct list sizes, the case of complete bipartite graphs

Abstract

Let $f:V\to \mathbb{N}$ be a function on the vertex set of the graph $G=(V,E)$. The graph $G$ is {\em $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, ${\chi }_{sc}(G)$, is the minimum of $\sum f(v)$, over all functions $f$ such that $G$ is $f$-choosable. It is known (Alon 1993, 2000) that if $G$ has average degree $d$, then the usual choice number ${\chi }_{\ell }(G)$ is at least $\Omega (\log d)$, so they grow simultaneously. In this paper we show that ${\chi }_{sc}(G)/|V(G)|$ can be bounded while the minimum degree ${\delta }_{\min }(G)\to \infty$. Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph $K_{a,q}$.

arXiv comment10 pages