Chromatic-choosability of hypergraphs with high chromatic number (Q668048)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic-choosability of hypergraphs with high chromatic number |
scientific article |
Statements
Chromatic-choosability of hypergraphs with high chromatic number (English)
0 references
5 March 2019
0 references
A vertex coloring of a hypergraph $H$ is proper if every edge contains a pair of vertices of different color. The chromatic number of $H$, denoted by $\chi(H)$, is the minimum number of colors needed for a proper coloring of $H$. For a natural number $k$ is a $k$-list assignment of $H$ a mapping $L$ which assigns to each vertex a set $L(v)$ of $k$ permissible colors. An $L$-coloring is a proper coloring of $H$ where the color for $v$ is chosen from $L(v)$. Hypergraph $H$ is $k$-choosable if an $L$-coloring exists for every $k$-list assignment and the list chromatic number $\chi_l(H)$ is the minimum $k$ for which $H$ is $k$ choosable. We say that $H$ is chromatic-choosable if $\chi(H)=\chi_l(H)$. \par The authors conjecture that $r$-uniform hypergraphs with high chromatic number are chromatic choosable, that is if $|V(H)|\leq r\chi(H)+r-1$, then $\chi(H)=\chi_l(H)$. This is a generalization of a conjecture for graphs from \textit{K. Ohba} [J. Graph Theory 40, No. 2, 130--135 (2002; Zbl 1004.05030)] which was proven by \textit{J. A. Noel} et al. [J. Graph Theory 79, No. 2, 86--102 (2015; Zbl 1320.05045)]. To underline the mentioned conjecture, two families of $r$-uniform hypergraphs are presented that show the sharpness of the conjecture, that is $|V(H)|=r\chi(H)+r$ and $\chi(H)<\chi_l(H)$. Also two families of $r$-uniform hypergraphs are presented that support the conjecture.
0 references
chromatic number
0 references
list chromatic number
0 references
hypergraphs
0 references
0 references