|
This article is cited in 2 scientific papers (total 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.
Received: 23.04.2015 Revised: 08.07.2015
Citation:
I. R. Shirgazina, “Equitable Colorings of Nonuniform Hypergraphs”, Mat. Zametki, 99:3 (2016), 441–456; Math. Notes, 99:3 (2016), 444–456
Linking options:
https://www.mathnet.ru/eng/mzm10790https://doi.org/10.4213/mzm10790 https://www.mathnet.ru/eng/mzm/v99/i3/p441
|
Statistics & downloads: |
Abstract page: | 329 | Full-text PDF : | 67 | References: | 83 | First page: | 53 |
|