  We study in this paper the structure of solutions in the random hypergraph
coloring problem and the phase transitions they undergo when the density of
constraints is varied. Hypergraph coloring is a constraint satisfaction problem
where each constraint includes $K$ variables that must be assigned one out of
$q$ colors in such a way that there are no monochromatic constraints, i.e.
there are at least two distinct colors in the set of variables belonging to
every constraint. This problem generalizes naturally coloring of random graphs
($K=2$) and bicoloring of random hypergraphs ($q=2$), both of which were
extensively studied in past works. The study of random hypergraph coloring
gives us access to a case where both the size $q$ of the domain of the
variables and the arity $K$ of the constraints can be varied at will. Our work
provides explicit values and predictions for a number of phase transitions that
were discovered in other constraint satisfaction problems but never evaluated
before in hypergraph coloring. Among other cases we revisit the hypergraph
bicoloring problem ($q=2$) where we find that for $K=3$ and $K=4$ the
colorability threshold is not given by the one-step-replica-symmetry-breaking
analysis as the latter is unstable towards more levels of replica symmetry
breaking. We also unveil and discuss the coexistence of two different 1RSB
solutions in the case of $q=2$, $K \ge 4$. Finally we present asymptotic
expansions for the density of constraints at which various phase transitions
occur, in the limit where $q$ and/or $K$ diverge.
