Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 407-413 |
Число страниц | 7 |
Журнал | Random Structures and Algorithms |
Том | 47 |
Номер выпуска | 3 |
DOI | |
Состояние | Опубликовано - 1 янв 2015 |
ID: 36098458