Biuniform hypergraph coloring

Бесплатный доступ

The paper deals with biuniform hypergraphs, i.e. hypergraphs of which edges are of two sizes. For the hypergraph H, let f(H) be an expected value of the number of monochromatic edges when blue and red colors are assigned to each vertex independently with probability 1/2. It is known that if the minimum edge size is at least k and f(H) C log k, then the proper coloring for H exists. In this paper, we consider f(H) for a coloring of the biuniform hypergraph H = (V, E1, E2) when there are no either red edges from E1 or blue ones from E2.

Hypergraph, proper coloring, biuniform hypergraph

Короткий адрес: https://sciup.org/142231009

IDR: 142231009   |   DOI: 10.53815/20726759_2021_13_3_23

Статья научная