RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2016 Volume 99, Issue 3, Pages 441–456 (Mi mzm10790)

This article is cited in 2 papers

Equitable Colorings of Nonuniform Hypergraphs

I. R. Shirgazina

Lomonosov Moscow State University

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_{e \in E}r^{1-|e|}\le c \sqrt{k}\,, $$
where $c>0$ is an absolute constant, then there exists an equitable $r$-coloring of $H$.

Keywords: hypergraph, equitable coloring, simple hypergraph.

UDC: 519.174.7+519.179.1

Received: 23.04.2015
Revised: 08.07.2015

DOI: 10.4213/mzm10790


 English version:
Mathematical Notes, 2016, 99:3, 444–456

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025