On the Choice Numbers of Some Complete Multipartite Graphs

摘要

For every vertex υ in a graph G, let L(υ) denote a list of colors assigned to v. A list coloring is a proper coloring f such that f(υ) ∈ L(υ) for all v. A graph is k-choosable if it admits a list coloring for every list assignment L with |L(υ)| = k. The choice number of G is the minimum k such that G is fc-choosable. We generalize a result (of [4]) concerning the choice numbers of complete bipartite graphs and 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 byprod- uct, we classify (ⅰ) completely those complete tripartite graphs .K_(2,2,m) and (ⅱ) almost completely those complete bipartite graphs K_(n,m) (for n ≤ 6) according to their choice numbers.