Equitable colorings of nonuniform hypergraphs

Abstract

The well-known extremal problem on hypergraph colorings is studied. We investigate whether it is possible to color a hypergraph with a fixed number of colors equitably, i.e., so that, on the one hand, no edge is monochromatic and, on the other hand, the cardinalities of the color classes are almost the same. It is proved that if H = (V,E) is a simple hypergraph in which the least cardinality of an edge equals k, |V| = n, r|n, and

\(\sum\limits_{e \in E} {{r^{1 - \left| e \right|}}} \leqslant c\sqrt k ,\)

where c > 0 is an absolute constant, then there exists an equitable r-coloring of H.