A note on random greedy coloring of uniform hypergraphs
The smallest number of edges forming an n-uniform hypergraph which is not r-colorable is denoted by m(n,r). Erd?s and Lovsz conjectured that . The best known lower bound was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on the analysis of a random greedy coloring algorithm investigated by Pluhr in 2009. The proof method extends to the case of r-coloring, and we show that for any fixed r we have improving the bound of Kostochka from 2004. We also derive analogous bounds on minimum edge degree of an n-uniform hypergraph that is not r-colorable.  2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 407413, 2015
coloring hypergraph greedy algorithm