Equitable coloring of hypergraphs

A hypergraph is equitably $k$-colorable if its vertices can be partitioned into $k$ sets (color classes) in such a way that monochromatic edges are avoided and the number of vertices in any two color classes differs by at most one. Such model is a direct generalization of well studied equitable graph coloring. However, the problem for hypergraphs has not been considered so far. Thus, we have established some initial complexity results. It has been proven that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. On the other hand for sparse systems like linear hypertrees the method of dynamic programing can be applied as long as $k \geq 2$ is fixed.