Randomly coloring simple hypergraphs with fewer colors

Michael Anastos, Alan Frieze

We study the problem of constructing a (near) uniform random proper $q$-coloring of a simple $k$-uniform hypergraph with $n$ vertices and maximum degree $\Delta$. (Proper in that no edg…