TY - JOUR

T1 - A note on random greedy coloring of uniform hypergraphs

AU - Cherkashin, Danila D.

AU - Kozik, Jakub

PY - 2015/1/1

Y1 - 2015/1/1

N2 - The smallest number of edges forming an n-uniform hypergraph which is not r-colorable is denoted by m(n,r). Erdos and Lovász conjectured that m(n,2)=Θ(n2n). The best known lower bound m(n,2)=Ω(n/ln(n)2n) 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 m(n,r)=Ω((n/ln(n))(r-1)/rrn) 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.

AB - The smallest number of edges forming an n-uniform hypergraph which is not r-colorable is denoted by m(n,r). Erdos and Lovász conjectured that m(n,2)=Θ(n2n). The best known lower bound m(n,2)=Ω(n/ln(n)2n) 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 m(n,r)=Ω((n/ln(n))(r-1)/rrn) 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.

KW - Coloring

KW - Greedy algorithm

KW - Hypergraph

UR - http://www.scopus.com/inward/record.url?scp=84939467821&partnerID=8YFLogxK

U2 - 10.1002/rsa.20556

DO - 10.1002/rsa.20556

M3 - Article

AN - SCOPUS:84939467821

VL - 47

SP - 407

EP - 413

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 3

ER -