Premium
On the asymptotic value of the choice number of complete multi‐partite graphs
Author(s) -
Gazit Nurit,
Krivelevich Michael
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20137
Subject(s) - combinatorics , mathematics , bipartite graph , interval (graph theory) , graph , discrete mathematics
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