Generalized Ohba conjecture for r-uniform hypergraphs: chromatic-choosability at high chromatic number

Wang and Qian (Electron. J. Combin. 26(1), 2019, #P1.5) proposed a hypergraph generalization of Ohba's conjecture: for every integer $r\ge2$ and every $r$-uniform hypergraph $H$, if $|V(H)|\le r\chi(H)+r-1$ then the list chromatic number equals the chromatic number, $\chi_l(H)=\chi(H)$. For $r=2$ this is exactly Ohba's conjecture for graphs, proved by Noel, Reed and Wu; for every $r\ge3$ the conjecture is open. The threshold is best possible, since Wang and Qian constructed $r$-uniform hypergraphs with $|V(H)|=r\chi(H)+r$ and $\chi_l(H)>\chi(H)$.

Background

In a hypergraph $H=(V,E)$, each edge is a subset of vertices of size at least 2; $H$ is $r$-uniform when every edge has exactly $r$ vertices, so a graph is a 2-uniform hypergraph. A proper vertex coloring of a hypergraph assigns colors so that no edge is monochromatic, and the chromatic number $\chi(H)$ is the least number of colors permitting such a coloring. In list coloring, introduced for graphs by Vizing and by Erdős, Rubin and Taylor, each vertex $v$ receives its own set (list) $L(v)$ of admissible colors, and a coloring is acceptable if it is proper and satisfies $f(v)\in L(v)$ for every vertex; the list chromatic number (choice number) $\chi_l(H)$ is the least $k$ such that an acceptable coloring exists for every assignment of lists of size at least $k$. Since assigning identical lists recovers ordinary coloring, $\chi_l(H)\ge\chi(H)$ always, and equality can fail badly: some bipartite graphs have arbitrarily large choice number. A structure with $\chi_l=\chi$ is called chromatic-choosable. Ohba conjectured in 2002 that graphs of relatively small order are nevertheless chromatic-choosable: if $|V(G)|\le2\chi(G)+1$ then $\chi_l(G)=\chi(G)$. This was proved by Noel, Reed and Wu (J. Graph Theory 79, 2015), and the bound cannot be relaxed, since complete multipartite graphs on $2\chi+2$ vertices with $\chi_l>\chi$ exist. Wang and Qian extended the story to uniform hypergraphs: they observed that hypergraphs of high chromatic number relative to their order are chromatic-choosable in certain regimes, showed that their proposed hypergraph analogue implies an earlier Ohba-like conjecture of Yan, Wang and Xue for $d$-improper colorings, and proved the conjectured threshold sharp. Here $d$-improper coloring means a coloring in which each vertex has at most $d$ same-colored neighbors, and $\chi^d$, $\chi_l^d$ are the corresponding parameters. The relevant test cases are the $r$-complete $k$-partite hypergraphs $K^r_{p_1,\ldots,p_k}$: the vertex set is partitioned into partite sets $V_i$ of sizes $p_i$, and the edges are all $r$-subsets that are not contained in any single partite set, so that every edge meets at least two partite sets. This convention, used by Wang and Qian (following Emtander), allows an edge to contain several vertices of one partite set and differs from the convention in parts of the hypergraph literature; for $r=2$ it coincides with the usual complete $k$-partite graph. For these hypergraphs, whenever $p_i\ge r-1$ for all $i$ with at most one exception, one has $\chi(K^r_{p_1,\ldots,p_k})=k$, and Wang and Qian observed that their conjecture holds in general if and only if it holds for these hypergraphs — the same reduction to complete multipartite graphs that drives the graph case. When a part size $a$ occurs $s$ times it is abbreviated $a*s$ in the sequel: for instance $K^r_{2r,r*(k-1)}$ has one partite set of size $2r$ and $k-1$ partite sets of size $r$, hence $rk+r$ vertices.

Problem Statement

Prove or refute the generalized Ohba conjecture of Wang and Qian: every $r$-uniform hypergraph $H$ with $|V(H)|\le r\chi(H)+r-1$ satisfies $\chi_l(H)=\chi(H)$. The case $r=2$ is known (it is Ohba's conjecture for graphs, proved by Noel, Reed and Wu), so the open content is $r\ge3$. By the reduction proved in the source paper, it is equivalent to settle the complete multipartite form: for all $r\ge2$ and positive integers $p_1,\ldots,p_k$ with $p_i\ge r-1$ for all but at most one $i$ and $\sum_i p_i\le rk+r-1$, the $r$-complete $k$-partite hypergraph $K^r_{p_1,\ldots,p_k}$, whose partite sets have sizes $p_1,\ldots,p_k$ and whose edges are all $r$-subsets not contained in a single partite set, satisfies $\chi_l(K^r_{p_1,\ldots,p_k})=k$. The threshold cannot be weakened, since $r$-uniform hypergraphs with $|V(H)|=r\chi(H)+r$ and $\chi_l(H)>\chi(H)$ are known; the question is exactly whether the bound $r\chi(H)+r-1$ guarantees chromatic-choosability for every uniformity $r\ge3$.

References

1. Wei Wang, Jianguo Qian, 'Chromatic-Choosability of Hypergraphs with High Chromatic Number', Electronic Journal of Combinatorics 26(1) (2019) #P1.5, DOI 10.37236/8070, https://doi.org/10.37236/8070 (arXiv:1807.08273, https://arxiv.org/abs/1807.08273)
2. Kyoji Ohba, 'On chromatic-choosable graphs', Journal of Graph Theory 40 (2002) 130-135, DOI 10.1002/jgt.10033, https://doi.org/10.1002/jgt.10033
3. Jonathan A. Noel, Bruce A. Reed, Hehui Wu, 'A Proof of a Conjecture of Ohba', Journal of Graph Theory 79 (2015) 86-102, DOI 10.1002/jgt.21819, https://doi.org/10.1002/jgt.21819 (arXiv:1211.1999, https://arxiv.org/abs/1211.1999)
4. Zhidan Yan, Wei Wang, Nini Xue, 'On Improperly Chromatic-Choosable Graphs', Graphs and Combinatorics 31 (2015) 1807-1814, DOI 10.1007/s00373-014-1438-9, https://doi.org/10.1007/s00373-014-1438-9
5. Wei Wang, Jianguo Qian, Zhidan Yan, 'Towards a Version of Ohba's Conjecture for Improper Colorings', Graphs and Combinatorics 33 (2017) 489-501, DOI 10.1007/s00373-017-1763-x, https://doi.org/10.1007/s00373-017-1763-x
6. Wei Wang, Jianguo Qian, Zhidan Yan, 'Colorings versus list colorings of uniform hypergraphs', Journal of Graph Theory 95 (2020) 384-397, DOI 10.1002/jgt.22550, https://doi.org/10.1002/jgt.22550
7. Marcin Anholcer, Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, Jakub Przybyło, Oriol Serra, Michał Tuczyński, Lluís Vena, Mariusz Zając, 'Alon-Tarsi for hypergraphs', arXiv:2501.00157 (2024; revised August 2026), https://arxiv.org/abs/2501.00157
8. D. A. Shabanov, T. M. Shaikheeva, 'The List-Chromatic Number of Complete Multipartite Hypergraphs and Multiple Covers by Independent Sets', Mathematical Notes 107 (2020) 499-508, DOI 10.1134/S000143462003013X, https://doi.org/10.1134/S000143462003013X
9. Kennedy Cano, Emily Gutknecht, Gautham Kappaganthula, George Miller, Jeffrey A. Mudrock, Ezekiel Thornburgh, 'On the Ohba Number and Generalized Ohba Numbers of Complete Bipartite Graphs', Graphs and Combinatorics 42 (2026), DOI 10.1007/s00373-026-03039-3, https://doi.org/10.1007/s00373-026-03039-3
10. Nandana K. Vasudevan, K. Somasundaram, N. Narayanan, 'List-Coloring and Chromatic-Choosability - A Dynamic Survey', arXiv:2606.31702 (2026), https://arxiv.org/abs/2606.31702