Loading...
Please wait, while we are loading the content...
Similar Documents
Chromatic-choosability of hypergraphs with high chromatic number
| Content Provider | arXiv |
|---|---|
| Author | Wang, Wei Qian, Jianguo |
| Date of Submission | 2018-07-22 |
| 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)$. |
| Related Links | https://arxiv.org/pdf/1807.08273.pdf |
| Page Count | 18 |
| arXiv | 1807.08273 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Mathematics - Combinatorics Coloring of graphs and hypergraphs Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
