Biuniform hypergraph coloring
Автор: Akhmejanova M.B.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 3 (51) т.13, 2021 года.
Бесплатный доступ
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