Polychromatic colorings of hypergraphs with high balance

Abstract

Let $m$ be a positive integer and $C = \{1,2,\dots,m\}$ be a set of $m$ colors. A polychromatic $m$-coloring of a hypergraph is a coloring of its vertices in such a way that every hyperedge contains at least one vertex of each color in $C$. This problem is a generalization of $2$-colorings of hypergraphs and has close relations with the longest lifetime problem for a wireless sensor network, cover decompositions problem of hypergraphs and vertex cover problem of hypergraphs. In this paper, a main work is to find the maximum $m$ that a hypergraph $H$, with $n$ hyperedges, admits a polychromatic $m$-coloring such that each color appears at least $k$ times on each hyperedge. A $2\ln n$ approximation to the number is obtained when $k$ is a fixed positive integer. For the case that $k=O(n\ln n)$, there exists an $O(\ln n)$ approximation algorithm; for the case that $k=\omega (n\ln n)$, there exists a $(2+\sqrt{3})k$ approximation algorithm.

Keywords

• hypergraph
• polychromatic coloring
• cover decomposition
• balanced coloring
• probabilistic method