Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653387 | European Journal of Combinatorics | 2015 | 19 Pages |
Abstract
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 Î(H) satisfying Î(H)⩽c2kâ1klnk for some absolute constant c>0, then H is 2-colorable. By using the Lovász 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dmitry A. Shabanov,