pith. sign in

arxiv: 1807.08273 · v1 · pith:GYIC736Snew · submitted 2018-07-22 · 🧮 math.CO

Chromatic-choosability of hypergraphs with high chromatic number

classification 🧮 math.CO
keywords hypergraphsuniformconjecturechromaticclasseshighnumberohba
0
0 comments X
read the original 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\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 give two classes of $r$-uniform hypergraphs $H$ with $|V(H)|= r\chi(H)+r-1$ and prove that $\chi_l(H)=\chi(H)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.