On the asymptotic value of the choice number of complete multi‐partite graphs

We calculate the asymptotic value of the choice number of complete multi‐partite graphs, given certain limitations on the relation between the sizes of the different sides. In the bipartite case, we prove that if n 0 ≤ n 1 and log n 0 ≫ loglog n 1 , then $ch(K_{n_{0},n_{1}}) = (1 + o(1)) {{\rm log}_{2}n_{1} \over {\rm log}_{2}x_{0}}$ , where x 0 is the unique root of the equation $x - 1 - x^{k-1 \over k} = 0$ in the interval $[1, \infty)$ and $k = {{{\rm log}_{2}n_1} \over {{\rm log}_{2}n_0}}$ . In the multi‐partite case, we prove that if $n_{0} \leq n_{1} \ldots \leq n_{s}$ , and n 0 is not too small compared to n s , then $ch(K_{n_{0}, \ldots, n_{s}}) = (1 + o(1)) {{\rm log}_{2}n_{s} \over {\rm log}_{2}x_{0}}$ . Here x 0 is the unique root of the equation $sx -1 - {\sum_{j=0}^{s-1}} \; x^{k_{j}-1 \over k_j} = 0$ in the interval $[1, \infty)$ , and for every $0 \leq i \leq s - 1$ , $k_{i} = {{\rm log}_{2} n_{s} \over {\rm log}_{2} n_{i}}$ . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 123–134, 2006