2018/07/22 by Wei Wang, Wang, Wei, Jianguo Qian +1
Computer Science · Engineering · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1807.08273
openalex publication_date 2018/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It was conjectured by Ohba and confirmed recently by Noel et al. that, for any graph G, if |V(G)|≤ 2χ(G)+1 then χl(G)=χ(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≥ 2, if |V(H)|≤ rχ(H)+r-1 then χl(H)=χ(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χ(H)+r and χl(H)>χ(H). To support the conjecture, we give two classes of r-uniform hypergraphs H with |V(H)|= rχ(H)+r-1 and prove that χl(H)=χ(H).