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

Article

Equitable two-colorings of uniform hypergraphs

European Journal of Combinatorics. 2015. Vol. 43. P. 185-203.

An equitable two-coloring of a hypergraph $H=(V,E)$ is a proper vertex two-coloring such that the cardinalities of color classes differ by at most one. In connection with the property B problem Radhakrishnan and Srinivasan proved that if $H$ is a $k$-uniform hypergraph with maximum vertex degree $\Delta(H)$ satisfying
$$
  \Delta(H)\leqslant c\,\frac {2^{k-1}}{\sqrt{k\,\ln k}}
$$
for some absolute constant $c>0$, then $H$ is 2-colorable. By using the Lov\'asz Local Lemma for negatively correlated events and the random recoloring method we prove that if $H$ either is a simple hypergraph or has a lot of vertices, then under the same condition on the maximum vertex degree it has an equitable coloring with two colors. We also obtain a general result for equitable colorings of partial Steiner systems.