• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Об алгоритмических методах исследования двухцветных раскрасок гиперграфов.

Лебедева А. В.

This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value m(k,n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains at least k vertices of each color. In this paper, we obtain upper bounds of m(k,n) for small k and n, the exact value of m(4,8), and a lower bound for m(3,7).