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

Article

On the weak chromatic number of random hypergraphs

Discrete Applied Mathematics. 2020. Vol. 276. P. 134-154.
Shabanov D. A., Semenov A.

The paper deals with weak chromatic numbers of random hypergraphs. Recall that a vertex coloring is said to be j-proper for a hypergraph if every j+1 vertices of any edge do not share a common color. The j-chromatic number of a hypergraph is the minimum number of colors required for a -proper coloring. We study the j-chromatic number of a random hypergraph in the binomial model H(n,k,p) in the case j=k-2 and investigate, for fixed k, the threshold for the property that j-chromatic number of does not exceed r. This threshold corresponds to the sparse case and the main result gives the tight bounds for it.