A note on random greedy coloring of uniform hypergraphs |
| |
| Authors: | Danila D. Cherkashin Jakub Kozik |
| |
| Affiliation: | Faculty of Mathematics and Mechanics, Saint‐Petersburg State University, Saint‐Petersburg, Russia |
| |
| Abstract: | The smallest number of edges forming an n‐uniform hypergraph which is not r‐colorable is denoted by m(n,r). Erd?s and Lovász 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 Pluhár 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, 407–413, 2015 |
| |
| Keywords: | coloring hypergraph greedy algorithm |
|
|
