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

Julian Allagan1, Peter Johnson2
1School of Science Technology Engineering and Mathematics, Gainesville State College, Watkinsville, GA- 30677, USA
2Department of Mathematics and Statistics 221 Parker Hall, Auburn University, AL – 36849, USA

Abstract

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