Equitable colorings of nonuniform hypergraphs.

Shirgazina, I.

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 where c > 0 is an absolute constant, then there exists an equitable r-coloring of H.

GRAPH coloring; HYPERGRAPHS; EDGES (Geometry); MATHEMATICAL inequalities; PROBABILITY theory; GEOMETRIC vertices

Mathematical Notes, 2016, Vol 99, Issue 3/4, p444

0001-4346

Academic Journal

10.1134/S0001434616030147