On the chromatic number of a random hypergraph

Martin Dyer, Alan Frieze, Catherine Greenhill

We consider the problem of $k$-colouring a random $r$-uniform hypergraph with $n$ vertices and $cn$ edges, where $k$, $r$, $c$ remain constant as $n$ tends to infinity. Achlioptas…