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

✍ Scribed by Nurit Gazit; Michael Krivelevich

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 144 KB
• Volume: 52
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20137

✦ Synopsis

Abstract

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