Choice number of some complete multi-partite graphs Original Research Article

One of the authors has conjectured that every graph G with 2χ(G)+1 or fewer vertices is χ(G)-choosable. Motivated by this, we investigate the choice numbers of some complete k-partite graphs of order slightly larger than 2k, and settle the conjecture for some special cases. We also present several complete multi-partite graphs whose choice numbers are not equal to their chromatic numbers.