On the Ohba Number and Generalized Ohba Numbers of Complete Bipartite Graphs

Abstract

We say that a graph $G$ is chromatic-choosable when its list chromatic number ${\chi }_{\ell }(G)$ is equal to its chromatic number $\chi (G)$. Chromatic-choosability is a well-studied topic, and in fact, some of the most famous results and conjectures related to list coloring involve chromatic-choosability. In 2002 Ohba showed that for any graph $G$ there is an $N\in \mathbb{N}$ such that the join of $G$ and a complete graph on at least $N$ vertices is chromatic-choosable. The Ohba number of $G$ is the smallest such $N$. In 2014, Noel suggested studying the Ohba number, ${\tau }_0(a,b)$, of complete bipartite graphs with partite sets of size $a$ and $b$. In this paper we improve a 2009 result of Allagan by showing that ${\tau }_0(2,b)=\lfloor \sqrt{b}\rfloor -1$ for all $b\ge 2$, and we show that for $a\ge 2$, ${\tau }_0(a,b)=\Omega (\sqrt{b})$ as $b\to \infty$. We also initiate the study of some relaxed versions of the Ohba number of a graph which we call generalized Ohba numbers. We present some upper and lower bounds of generalized Ohba numbers of complete bipartite graphs while also posing some questions.

15 pages