On the Ohba Number of K_{3,b}: Exact Values for b ≤ 8 by a Certified Exhaustive Search

For integers \(a,b\ge2\) let \(\varphi(a,b)\) be the least \(t\ge0\) such that the join \(K_{a,b}+K_t\) of the complete bipartite graph \(K_{a,b}\) with the complete graph \(K_t\) is chromatic-choosable, that is, \((t+2)\)-choosable. This is the Ohba number \(\tau_0(a,b)\) of \(K_{a,b}\); to determine it is a question of the Open Problem Garden, attributed there to J. Allagan and posted by J. Noel. The case \(a=2\) was settled by Cano, Gutknecht, Kappaganthula, Miller, Mudrock and Thornburgh, who also showed by a construction that \(K_{3,b}+K_t\) is not \((t+2)\)-choosable when \(t\ge1\) and \(b\ge1+(t+2)\lceil (t+2)/2\rceil\); a theorem of J. Zhu and X. Zhu implies that \(K_{3,b}+K_t\) is \((t+2)\)-choosable when \(t\ge1\) and \(b\le t+3\). Let \(N_3(t)\) be the least \(b\) for which \(K_{3,b}+K_t\) is not \((t+2)\)-choosable. We prove, by a computer-assisted exhaustive search with exact certificates, that \(K_{3,6}+K_1\) is \(3\)-choosable and that \(K_{3,8}+K_2\) is \(4\)-choosable. With the construction this gives \(N_3(1)=7\) and \(N_3(2)=9\), hence \(\varphi(3,b)=\varphi(b,3)=1\) for \(3\le b\le6\), \(\varphi(3,b)=\varphi(b,3)=2\) for \(b\in\{7,8\}\), and \(\varphi(3,b)\ge3\) for \(b\ge9\). The search reduces the question to a covering problem for the lists of the \(t+3\) vertices outside the part of size \(b\), runs, up to renaming of colours, through all these lists in which no colour is common to the three vertices of the part of size \(3\) (the others are settled at once; \(551\) cases for \(t=1\), \(297{,}955\) for \(t=2\)), and settles every case either by counting configurations or by one of \(18\), respectively \(435\), dual solutions of a linear program, which are verified in exact rational arithmetic; the certificates and a program that checks them in less than a minute are provided. No novelty is claimed for the values \(\varphi(3,b)\), \(5\le b\le8\): they were not found in the sources read (the problem page, the two papers named above, a 2026 survey and two zbMATH entries), but Allagan's 2009 thesis, which according to its abstract treats the Ohba numbers of the graphs \(K(m,n,1,\dots,1)=K_{m,n}+K_t\), could not be consulted and may contain some of them; neither could two 2015 papers of Allagan with coauthors and a 2007 paper of G. L. Chia and V. L. Chia. We conjecture that \(N_3(t)=1+(t+2)\lceil (t+2)/2\rceil\) for all \(t\); for \(t=3\) this is supported only by searches without certificates. The general question remains open. This is an unrefereed note.