Chromatic-choosability of hypergraphs with high chromatic number

Abstract

It was conjectured by Ohba and confirmed recently by Noel et al. that, for any graph $G$, if $|V(G)|\le 2\chi (G)+1$ then ${\chi }_l(G)=\chi (G)$. This indicates that the graphs with high chromatic number are chromatic-choosable. We show 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\ge 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 give two classes of $r$-uniform hypergraphs $H$ with $|V(H)|=r\chi (H)+r-1$ and prove that ${\chi }_l(H)=\chi (H)$.

18 pages