Estimates of the choice numbers and the Ohba numbers of some complete multipartite graphs. (Q2804793)

The Ohba number of a graph \(G\) is defined as the smallest integer \(n\) such that the join \(G\vee K_n\) satisfies \(\operatorname{ch}(G\vee K_n)=\chi (G\vee K_n)\), where \(\operatorname{ch}(G)\) and \(\chi (G)\) are the choice number and chromatic number of \(G\), respectively [\textit{K. Ohba}, J. Graph Theory 40, No. 2, 130--135 (2002; Zbl 1004.05030)]. In this paper, some estimates of the choice numbers and Ohba numbers of the complete multipartite graphs \(K(m,n,1,\dots ,1)\) and \(K(m,n,2,\dots ,2)\) are given for various values of \(m\geq n\geq 1\). For example, for complete \(k\)-partite graphs we have \(\operatorname{ch}(K(m,n,1,\dots ,1))\leq n+k-1\), \(\operatorname{ch}(K(m,2,\dots ,2))\leq 2k-1\) and equality holds for \(m\geq {{2k-2}\choose {k-1}}^{2}\).