Choosability of multipartite hypergraphs

Abstract

A $k$-uniform hypergraph (or $k$-graph) $H=(V,E)$ is $k$-partite if $V$ can be partitioned into $k$ sets $V_1,\dots ,V_k$ such that each edge in $E$ contains precisely one vertex from each $V_i$. We show that $k$-partite $k$-graphs of maximum degree $\hat{I}”$ are $q$-choosable for $q\ge {\left(\frac{4}{5}(k-1+o(1))\hat{I}”/\log \hat{I}”\right)}^{1/(k-1)}$. Our proof yields an efficient randomized algorithm for finding such a coloring, which shows that the conjectured algorithmic barrier for coloring pseudorandom $k$-graphs does not apply to $k$-partite $k$-graphs.

12 pages plus references