It was conjectured by Ohba and confirmed by Noel, Reed and Wu that, for any graph $G$, if $|V(G)|\le 2\chi(G)+1$ then $G$ is chromatic-choosable; i.e., it satisfies $\chi_l(G)=\chi(G)$. This indicates that the graphs with high chromatic number are chromatic-choosable. We observe that this is also the case for uniform hypergraphs and further propose a generalized version of Ohba's conjecture: for any $r$-uniform hypergraph $H$ with $r\geq 2$, if $|V(H)|\le r\chi(H)+r-1$ then $\chi_l(H)=\chi(H)$. We show that the condition of the proposed conjecture is sharp by giving two classes of $r$-uniform hypergraphs $H$ with $|V(H)|= r\chi(H)+r$ and $\chi_l(H)>\chi(H)$. To support the conjecture, we prove that $\chi_l(H)=\chi(H)$ for two classes of $r$-uniform hypergraphs $H$ with $|V(H)|= r\chi(H)+r-1$.
@article{10_37236_8070,
author = {Wei Wang and Jianguo Qian},
title = {Chromatic-choosability of hypergraphs with high chromatic number},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {1},
doi = {10.37236/8070},
zbl = {1411.05096},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8070/}
}
TY - JOUR
AU - Wei Wang
AU - Jianguo Qian
TI - Chromatic-choosability of hypergraphs with high chromatic number
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8070/
DO - 10.37236/8070
ID - 10_37236_8070
ER -
%0 Journal Article
%A Wei Wang
%A Jianguo Qian
%T Chromatic-choosability of hypergraphs with high chromatic number
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8070/
%R 10.37236/8070
%F 10_37236_8070
Wei Wang; Jianguo Qian. Chromatic-choosability of hypergraphs with high chromatic number. The electronic journal of combinatorics, Tome 26 (2019) no. 1. doi: 10.37236/8070
