Research output: Contribution to journal › Article › peer-review
A note on random greedy coloring of uniform hypergraphs. / Cherkashin, Danila D.; Kozik, Jakub.
In: Random Structures and Algorithms, Vol. 47, No. 3, 01.01.2015, p. 407-413.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 36098458