Equitable coloring of k-uniform hypergraphs

Abstract

Let $H$ be a $k$-uniform hypergraph with $n$ vertices. A {\em strong $r$-coloring} is a partition of the vertices into $r$ parts, such that each edge of $H$ intersects each part. A strong $r$-coloring is called {\em equitable} if the size of each part is $\lceil n/r\rceil$ or $\lfloor n/r\rfloor$. We prove that for all $a\ge 1$, if the maximum degree of $H$ satisfies $\Delta (H)\le k^a$ then $H$ has an equitable coloring with $\frac{k}{a\ln k}(1-o_k(1))$ parts. In particular, every $k$-uniform hypergraph with maximum degree $O(k)$ has an equitable coloring with $\frac{k}{\ln k}(1-o_k(1))$ parts. The result is asymptotically tight. The proof uses a double application of the non-symmetric version of the Lovász Local Lemma.

10 Pages