Estimates of the Choice Numbers and the Ohba Numbers of Some Complete Multipartite Graphs

Abstract

Estimates of the choice numbers and the Ohba numbers of the complete multipartite graphs $K(m,n,1,\dots ,1)$ and $K(m,n,2,\dots ,2)$ are provided for various values of $m\ge n\ge 1$. The Ohba number of a graph $G$ is the smallest integer $n$ such that $\mathrm{ch}(G\vee K_n)=\chi (G\vee K_n)$.