Equitable colorings of hypergraphs with limitation on vertex degree

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

The article deals with a problem of equitable colorings of uniform hypergraphs with bounded maximal vertex degrees. Let H = (V, E) be a hypergraph. A vertex r-coloring of the vertex set V is said to be equitable if each of the edges of E is not monochromatic under this coloring and moreover the cardinalities of every two color classes differ at most by one. We improve the bound for maximal vertex degree of a k-uniform hypergraph, which guarantees the existence of an equitable coloring with r > 2 colors provided that the number of vertices is large enough.

Hypergraphs, colorings of hypergraphs, equitable colorings, probabilistic method

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

IDR: 142238159

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