We say that a graph G is chromatic-choosable when its list chromatic number <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\chi _{\ell }(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>ℓ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is equal to its chromatic number <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\chi (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$N \in \mathbb {N}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>N</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> 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, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\tau _{0}(a,b)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>τ</mi> <mn>0</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\tau _{0}(2,b) = \lfloor \sqrt{b} \rfloor - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>τ</mi> <mn>0</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo>⌊</mo> <msqrt> <mi>b</mi> </msqrt> <mo>⌋</mo> </mrow> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$b \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>b</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, and we show that for <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$a \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>a</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\tau _{0}(a,b) = \Omega ( \sqrt{b} )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>τ</mi> <mn>0</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi mathvariant="normal">Ω</mi> <mrow> <mo stretchy="false">(</mo> <msqrt> <mi>b</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> as <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$b \rightarrow \infty $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>b</mi> <mo stretchy="false">→</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>. 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.

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

期刊论文
发表日期：

2026年4月6日

查看全文

Kennedy Cano,
Emily Gutknecht,
Gautham Kappaganthula,
George Miller,
Jeffrey A. Mudrock,
Ezekiel Thornburgh

摘要

We say that a graph G is chromatic-choosable when its list chromatic number $\chi _{\ell }(G)$ $χ_{ℓ} (G)$ is equal to its chromatic number $\chi (G)$ $χ (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}$ $N \in 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)$ $τ_{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$ $τ_{0} (2, b) = ⌊ \sqrt{b} ⌋ - 1$ for all $b \ge 2$ $b \geq 2$ , and we show that for $a \ge 2$ $a \geq 2$ , $\tau _{0}(a,b) = \Omega ( \sqrt{b} )$ $τ_{0} (a, b) = Ω (\sqrt{b})$ as $b \rightarrow \infty $ $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.