On the Choice Number of Some Complete Multi-partite Graphs

G.L. Chia and V.L. Chia
nstitute of Mathematical Sciences,
University of Malaya, 50603 Kuala Lumpur, Malaysia
Abstract

For every vertex v in a graph G, let L(v) denote a list of colors assigned to v. A list coloring is a proper coloring f such that f(v)\in L(v) for all v. A graph is k-{\it choosable} if it admits a list coloring for every list assignment L with |L(v)| = k. The choice number of G is the minimum k such that G is k-choosable. We prove some uniqueness results concerning the list colorability of the complete (k+1)-partite graph K_n,...,n,m. Using these, we determine the choice numbers for some complete multipartite graphs K_n,...,n,m. As a byproduct, we classify those complete bipartite graphs K_n,m (for n4) and those complete tripartite graphs K_2,2,m according to their choice numbers.